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

题目的主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM23.二叉树的前序遍历

BM24.二叉树的中序遍历

方法一：递归（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

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

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

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

具体做法：

• step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
• step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
• step 3：左子树访问完毕再进入根节点的右子树递归访问。
• step 4：最后回到根节点，访问该节点。

Java实现代码：

import java.util.*;
public class Solution {
    public void postorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        postorder(list, root.left); 
        //再去右子树
        postorder(list, root.right); 
        //最后访问根节点
        list.add(root.val); 
    }
    
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归后序遍历
        postorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

C++实现代码：

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;
    }
};

Python实现代码

class Solution:
    def postorder(self, list: List[int], root: TreeNode):
        # 遇到空节点则返回
        if not root:
            return
        # 先去左子树
        self.postorder(list, root.left) 
        # 再去右子树
        self.postorder(list, root.right) 
        # 最后访问根节点
        list.append(root.val) 
        
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        res = []
        # 递归后序遍历
        self.postorder(res, root) 
        return res

复杂度分析：

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

方法二：非递归（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

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

根据后序遍历“左右中”的顺序，那么后序遍历也与中序遍历类似，要先找到每棵子树的最左端节点：

//每次找到最左节点
while(root != NULL){ 
    s.push(root);
    root = root->left;
}

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

我们都知道从栈中弹出根节点，一定是左节点已经被访问过了，因为左节点是子问题，访问完了才回到父问题，那么我们还必须要确保右边也已经被访问过了。如果右边为空，那肯定不用去了，如果右边不为空，那我们肯定优先进入右边，此时再将根节点加入栈中，等待右边的子树结束。

//该节点再次入栈
s.push(node);
//先访问右边
root = node->right;

不过，当右边被访问了，又回到了根，我们的根怎么知道右边被访问了呢？用一个前序指针pre标记一下，每个根节点只对它的右节点需要标记，而每个右节点自己本身就是一个根节点，因此每次访问根节点的时候，我们可以用pre标记为该节点，回到上一个根节点时，检查一下，如果pre确实是它的右子节点，哦那正好，刚刚已经访问过了，我现在可以安心访问这个根了。

//如果该元素的右边没有或是已经访问过
if(node->right == NULL || node->right == pre){ 
    //访问中间的节点
    res.push_back(node->val); 
    //且记录为访问过了
    pre = node; 
}

具体做法：

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

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        while(root != null || !s.isEmpty()){ 
            //每次先找到最左边的节点
            while(root != null){ 
                s.push(root);
                root = root.left;
            }
            //弹出栈顶
            TreeNode node = s.pop(); 
            //如果该元素的右边没有或是已经访问过
            if(node.right == null || node.right == pre){ 
                //访问中间的节点
                list.add(node.val); 
                //且记录为访问过了
                pre = node; 
            }else{
                //该节点入栈
                s.push(node); 
                //先访问右边
                root = node.right; 
            }
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

C++实现代码：

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;
    }
};

Python实现代码

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # 添加遍历结果的数组
        res, s = [], [] 
        pre = None
        while root or s:
            # 每次先找到最左边的节点
            while root: 
                s.append(root)
                root = root.left
            # 弹出栈顶
            node = s[-1] 
            s.pop()
            # 如果该元素的右边没有或是已经访问过
            if not node.right or node.right is pre: 
                # 访问中间的节点
                res.append(node.val) 
                # 且记录为访问过了
                pre = node 
            else:
                # 该节点入栈
                s.append(node) 
                # 先访问右边
                root = node.right 
        return res

复杂度分析：

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