LeetCode刷题-二叉树遍历迭代法

LeetCode题目链接

二叉树的前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/
二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/
二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/

二叉树的遍历方法有两种，分别是递归法和迭代法；实际使用中由于系统调用栈有限制，使用递归法可能会导致栈溢出，这里记录三种遍历的迭代做法。最后，介绍二叉树层序遍历的两种方法。

迭代遍历法借助辅助栈实现，下面是二叉树节点的定义，使用链表实现。

 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 {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root == NULL) {
            return res;
        }

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

        return res;
    }
};

中序遍历

中序遍历处理顺序为左中右，先访问二叉树顶部的节点，随后逐层向下访问直到树最左侧的节点，再开始处理节点，这导致处理节点的顺序和访问节点的顺序不一致。中序遍历的迭代法如下所示：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root == NULL) {
            return res;
        }
        TreeNode *cur = root;
        while (cur!=NULL || !st.empty()) {
            if (cur != NULL) {
                if (cur) st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

后序遍历

先序遍历是中左右，后续遍历是左右中，那么只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。后序遍历的代码如下所示：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root == NULL) {
            return res;
        }
        st.push(root);
        while (!st.empty()) {
            TreeNode *cur = st.top();
            st.pop();
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
            res.push_back(cur->val);
        }
        reverse(res.begin(), res.end());
        return res;   
    }
};

统一的迭代遍历法

参考https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html
每次在待处理节点入栈后，加入一个NULL节点作为标记，之后在遇到NULL节点时处理栈中的下一个节点。需要注意的是，这种方法效率不高，节点可能会多次入栈。

层序遍历

// 迭代遍历，BFS基于队列
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root == NULL)  {
            return res;
        }

        q.push(root);
        while (!q.empty()) {
            int size =q.size();
            vector<int> layer;
            for (int i = 0; i < size; ++i) {
                TreeNode *cur = q.front();
                q.pop();
                layer.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            res.push_back(layer);
        }
        return res;
    }
};

// 递归，DFS
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root == NULL)  {
            return res;
        }

        order(0, root, res);
        return res;
    }

    // DFS, 递归
    void order(int depth, TreeNode *cur, vector<vector<int>> &res) {
        if (cur == NULL) return;
        if (res.size() == depth) res.push_back(vector<int>());
        res[depth].push_back(cur->val);
        order(depth + 1, cur->left, res);
        order(depth + 1, cur->right, res);
    }
};