145. Binary Tree Postorder Traversal.md

145. Binary Tree Postorder Traversal

思路

二叉树的后序遍历。递归方式很简单，这里主要讨论非递归方式。

思路一

除了层序遍历，二叉树的前序、中序、后序遍历的非递归算法一般都是用栈。后序遍历中比较特殊的是每个节点会有两次出现在栈顶：

1. 第一次是当其左右子树都还没访问时，所以应该按序将其右、左子树入栈（注意不会将该结点出栈）；
2. 第二次是当其左右子树都遍历完毕时，所以应该将其出栈并访问。

可见我们需要记录一下每个结点是否已经在栈顶出现过一次了，可用hashset来记录。

思路二

思路一需要一个hashset来记录某个结点的左右子树是否已经访问完毕（即之前是否在栈顶出现过），空间复杂度比较大。

其实可以用一个指针pre达到上述目的，用pre指向前一个遍历的节点，栈顶元素分如下三种情况：

1. 如果栈顶元素是叶子，那么直接出栈并访问然后更新pre；
2. 如果栈顶元素的左孩子或右孩子是pre，说明左右子树都已经处理完毕，那么应该将当前元素出栈并访问然后更新pre；
3. 否则，说明左右子树还未访问，将左右孩子入栈。

需要说明的是pre的初始值原则上任意都可以，但是其实不能为NULL，否则如果某结点有一个空孩子，那么就会满足上面的第2个条件，这是不对的。 同理也不能初始化为树中其他结点以免错误判断上面的第2个条件（初始为root是可以的）。

思路三、修改前序遍历

我们知道前序遍历是按照"根左右"的原则遍历的，而后序遍历则是按照"左右根"的遍历原则。那么我们可以稍加修改前序遍历的代码，使其按照"根右左"遍历，最后再将结果翻转就得到了"左右根"遍历结果。

C++

思路一

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        stack<TreeNode *>stk{{root}};
        set<TreeNode *>flag;
        TreeNode *p = NULL;
        while(!stk.empty()){
            p = stk.top();
            if(flag.find(p) == flag.end()){ // 第一次出现在栈顶
                flag.insert(p);
                if(p -> right) stk.push(p -> right);
                if(p -> left) stk.push(p -> left);
            }
            else{ // 第二次出现在栈顶
                res.push_back(p -> val);
                stk.pop();
            }
        }
        return res;
    }
};

思路二

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        stack<TreeNode *>stk{{root}};
        TreeNode *p = NULL, *pre = root; // pre不能为NULL!!
        while(!stk.empty()){
            p = stk.top();
            if((!p -> left && !p -> right) || p -> left == pre || p -> right == pre){
                res.push_back(p -> val);
                stk.pop();
                pre = p;
            }
            else{
                if(p -> right) stk.push(p -> right);
                if(p -> left) stk.push(p -> left);
            }
        }
        return res;
    }
};

思路三

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        stack<TreeNode *>stk{{root}};
        TreeNode *p = NULL;
        while(!stk.empty()){
            p = stk.top(); stk.pop();
            res.push_back(p -> val);
            // 前序遍历这里是先右后左
            if(p -> left) stk.push(p -> left); 
            if(p -> right) stk.push(p -> right);
        }
        
        reverse(res.begin(), res.end()); // 前序遍历无这句
        return res;
    }
};