leetcode 145.二叉树的后序遍历

这道题可以用递归写，比较简单，但是 我想用非递归写，这是有点挑战难度的：

• 审题：给一个二叉树的根节点 返回它的后序遍历。
• 思路：可以用栈来实现非递归版本的，后序遍历是 左 右 根
• 图解：

1. 初始条件 是 这棵二叉树，cur是现在访问的节点，prev是上一次访问的节点
   
2. 因为是 左 右 根，所以 只要左子树 存在就要 入栈
   
3. 现在cur为空，也就是说 左子树节点都入到栈中了，取出 栈顶数据，判断 它的右子树是否存在，如果右子树存在 继续 入栈右子树 ；如果右子树不存在或者右子树为 prev 那么就将此栈顶数据 保存到 数组中，并pop出栈顶数据，并更新prev。

现在栈顶数据是 4，它的右子树为空，所以可以保存到vector中：

4. 继续取出栈顶数据，也就是 2 ，它的右子树存在，并且prev不是它，所以 2 节点不能出栈，继续它的右子树：
   

5. 由于 5的左右都为空，所以 5 就能直接出栈，并更新prev：
   

6. 继续取出栈顶元素，判断它能不能出栈，发现它的右树是prev，所以它的右子树已经访问过了，它的左右子树都被访问，所以 它可以出栈，更新prev:

7. 取出栈顶元素，发现 1 节点的右子树 不为空，并且它的右子树 还不是 prev，说明需要将其右子树入栈，更新cur：

8. cur的左右子树都为空，所以 直接出栈，并更新 prev：

9. 继续取栈顶元素 1 ，发现它的右子树为prev，所以它也可以出栈，它出栈成功后，栈为空，所以可以退出循环：
   
10. 总结：
    入栈就得更新cur，出栈就得更新prev。
    并且出栈的条件就是 其右子树为空或者右子树为prev，原因就是 表明它的左右子树都已经出栈了，它才能出栈。

• 代码实现：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> stack_;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        vector<int> ret;
        while(cur||!stack_.empty())
        {
             左 右 根
                
            while(cur)
            {
              stack_.push(cur);
              cur = cur->left;
            }
            TreeNode* top = stack_.top();
            if(top->right==nullptr || top->right== prev)
            {
                ret.push_back(top->val);
                prev = top;
                stack_.pop();
            }
            else
            {
                cur = top->right;
            }

        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33