算法刷题Day14 二叉树的前序、中序、后序遍历（递归、迭代、统一迭代方法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法刷题Day14 二叉树的前序、中序、后序遍历（递归、迭代、统一迭代方法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Day 14 二叉树

二叉树的定义

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

前序遍历

递归

class Solution {
    void traverse(TreeNode *root, vector<int> &arr)
    {
        if (root == nullptr) return;
        arr.push_back(root->val);
        traverse(root->left, arr);
        traverse(root->right, arr);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rst;
        traverse(root, rst);
        return rst;
    }
};

迭代

普通的遍历（包括前序，中序和后续）迭代方法都需要借助到栈

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        vector<int> rst;
        stack<TreeNode*> stk;

        stk.push(root);
        TreeNode *cur;
        while (!stk.empty())
        {
            cur = stk.top();
            stk.pop();
            rst.push_back(cur->val);
            
            if (cur->right) stk.push(cur->right);
            if (cur->left) stk.push(cur->left);
        }

        return rst;
    }
};

统一迭代

统一迭代使用标记法，在栈中要处理的结点压入空指针

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> rst;
        stack<TreeNode*> stk;
        if (root) stk.push(root);
        TreeNode *cur;

        while (!stk.empty())
        {
            cur = stk.top();
            stk.pop();
            if (cur)
            {
                if (cur->right) stk.push(cur->right);
                if (cur->left) stk.push(cur->left);
                stk.push(cur);
                stk.push(nullptr);
            }
            else
            {
                cur = stk.top();
                stk.pop();
                rst.push_back(cur->val);
            }
        }

        return rst;
    }
};

中序遍历

递归

class Solution {
    void traverse(TreeNode *root, vector<int> &arr)
    {
        if (root == nullptr) return;
        traverse(root->left, arr);
        arr.push_back(root->val);
        traverse(root->right, arr);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rst;
        traverse(root, rst);
        return rst;
    }
};

迭代

中序遍历的迭代方法稍微特殊一点

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点，这就造成了处理顺序和访问顺序是不一致的。

在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};

        stack<TreeNode*> stk;
        vector<int> rst;
        TreeNode *cur = root;

        while (cur || !stk.empty())
        {
            if (cur)
            {
                stk.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = stk.top();
                stk.pop();
                rst.push_back(cur->val);
                cur = cur->right;
            }
        }

        return rst;
    }
};

统一迭代

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> rst;
        stack<TreeNode*> stk;
        if (root) stk.push(root);
        TreeNode *cur;

        while (!stk.empty())
        {
            cur = stk.top();
            stk.pop();
            if (cur)
            {                
                if (cur->right) stk.push(cur->right);
                stk.push(cur);
                stk.push(nullptr);
                if (cur->left) stk.push(cur->left);
            }
            else
            {
                cur = stk.top();
                stk.pop();
                rst.push_back(cur->val);
            }
        }

        return rst;
    }
};

后序遍历

递归

class Solution {
    void traverse(TreeNode *root, vector<int> &arr)
    {
        if (root == nullptr) return;
        traverse(root->left, arr);
        traverse(root->right, arr);
        arr.push_back(root->val);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rst;
        traverse(root, rst);
        return rst;
    }
};

迭代

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了文章来源地址https://www.toymoban.com/news/detail-555125.html

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        stack<TreeNode*> stk;
        TreeNode *cur;
        vector<int> rst;
        stk.push(root);

        while (!stk.empty())
        {
            cur = stk.top();
            stk.pop();
            rst.push_back(cur->val);
            if (cur->left) stk.push(cur->left);
            if (cur->right) stk.push(cur->right);
        }

        reverse(rst.begin(), rst.end());
        return rst;
    }
};

统一迭代

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> rst;
        stack<TreeNode*> stk;
        if (root) stk.push(root);
        TreeNode *cur;

        while (!stk.empty())
        {
            cur = stk.top();
            stk.pop();
            if (cur)
            {
                stk.push(cur);
                stk.push(nullptr);
                if (cur->right) stk.push(cur->right);
                if (cur->left) stk.push(cur->left);
            }
            else
            {
                cur = stk.top();
                stk.pop();
                rst.push_back(cur->val);
            }
        }

        return rst;
    }
};