关于二叉树的遍历，有递归法和迭代法两种。递归法简单易懂，但是迭代法较为复杂，需要使用栈来模拟递归的过程。

这里以“将二叉树按某种顺序遍历输出”为例，介绍迭代法的实现。

关键在于理解某个节点输出的时机。

1. 前序遍历

先输出，再将左子节点入栈。没有左子节点了，才考虑右子节点的入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        while(!stk.empty() || root!=nullptr){
            while(root!=nullptr){
                ans.push_back(root->val);
                stk.emplace(root);
                root=root->left;
            }
            root=stk.top()->right;
            stk.pop();
        }
        return ans;
    }

2. 中序遍历

先将左子节点入栈，没有左子节点了，才输出当前节点（栈顶节点），然后考虑（栈顶节点的）右子节点的入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        while(!stk.empty() || root!=nullptr){
            while(root!=nullptr){
                stk.emplace(root);
                root=root->left;
            }
            root=stk.top();
            stk.pop();
            ans.push_back(root->val);
            root=root->right;
        }
        return ans;
    }

3. 后序遍历

先将左子节点入栈，没有左子节点了，才考虑右子节点的入栈。如果右子节点也没有了，才输出当前节点。

难点：如何判断当前节点的右子节点是否已经遍历过了？

  • 使用一个指针prev来记录上一个遍历的节点。
  • 如果当前节点的右子节点为空，或者右子节点已经遍历过了，才输出当前节点。
  • 否则，将右子节点入栈，然后考虑左子节点的入栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*>stk;
        TreeNode* prev=nullptr;
        while(!stk.empty()||root!=nullptr){
            while(root!=nullptr){
                stk.emplace(root);
                root=root->left;
            }
            root=stk.top();
            if(root->right==nullptr || root->right==prev){
                ans.push_back(root->val);
                prev=root;
                stk.pop();
                root=nullptr; // 这里很重要！否则会因为root不为空而“入栈-出栈”无限循环
            }
            else{
                root=root->right;
            }
        }
        return ans;
    }