题解 | #二叉树的后序遍历#

题目的主要信息：

给定一颗二叉树的根节点，输出其后序遍历的结果

方法一：递归

具体做法：

什么是二叉树的后续遍历，简单来说就是“左右根”，展开来说就是优先访问根节点的左子树的全部节点，然后再访问根节点的右子树的全部节点，最后再访问根节点。对于每棵子树的访问也按照这个逻辑，因此叫做“左右根”的顺序。

从上述后序遍历的解释中我们不难发现，它存在递归的子问题：对每个子树的访问，可以看成对于上一级树的子问题。那我们可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 对于每个子问题，优先进入左子树的子问题，访问完了再进入右子树的子问题，最后回到父问题访问根节点。

class Solution {
public:
    void postorder(vector<int> &res, TreeNode* root){
        if(root == NULL) //遇到空节点则返回
            return;
        postorder(res, root->left); //先遍历左子树
        postorder(res, root->right); //再遍历右子树
        res.push_back(root->val); //最后遍历根节点
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(res, root);  //递归后序遍历
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历二叉树所有节点
空间复杂度： $O (n)$ ，最坏情况下二叉树化为链表，递归栈深度为 $n$

方法二：非递归

具体做法：

既然二叉树的前序遍历和中序遍历都可以使用栈来代替递归，那后序遍历是否也可以呢？答案是可以的，但是会比前二者复杂一点点。

根据后序遍历“左右中”的顺序，那么后序遍历也与中序遍历类似，要先找到每棵子树的最左端节点，然后我们就要访问该节点了嘛？不不不，如果它还有一个右节点呢？根据“左右根”的原则，我还要先访问右子树。我们只能说它是最左端的节点，它左边为空，但是右边不一定，因此这个节点必须被看成是这棵最小的子树的根。要怎么访问根节点呢？

我们都知道从栈中弹出根节点，一定是左节点已经被访问过了，因为左节点是子问题，访问完了才回到父问题，那么我们还必须要确保右边也已经被访问过了。如果右边为空，那肯定不用去了，如果右边不为空，那我们肯定优先进入右边，此时再将根节点加入栈中，等待右边的子树结束。不过，当右边被访问了，又回到了根，我们的根怎么知道右边被访问了呢？用一个前序指针pre标记一下，每个根节点只对它的右节点需要标记，而每个右节点自己本身就是一个根节点，因此每次访问根节点的时候，我们可以用pre标记为该节点，回到上一个根节点时，检查一下，如果pre确实是它的右子节点，哦那正好，刚刚已经访问过了，我现在可以安心访问这个根了。

step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。

具体过程如下图所示：

alt

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s; //辅助栈
        TreeNode* pre = NULL; 
        while(root != NULL || !s.empty()){ 
            while(root != NULL){ //每次先找到最左边的节点
                s.push(root);
                root = root->left;
            }
            TreeNode* node = s.top(); //弹出栈顶
            s.pop();
            if(node->right == NULL || node->right == pre){ //如果该元素的右边没有或是已经访问过
                res.push_back(node->val); //访问中间的节点
                pre = node; //且记录为访问过了
            }else{
                s.push(node); //该节点入栈
                root = node->right; //先访问右边
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历二叉树所有节点
空间复杂度： $O (n)$ ，辅助栈空间最大为链表所有节点数