二叉树的后序遍历 图解题解

这道题到底在问什么

输入

root=[1,null,2,3]

输出

[3,2,1]

输入

root=[1,2,3,4,5]

输出

[4,5,2,3,1]

最优解：一步一步想明白

1. 3记住「先左、再右、最后才记根」,记根的语句放在两个递归调用之后。下面逐帧走一遍这棵树。
2. 4整棵树先看清这棵树:根是 50,它的左孩子 30(下面挂着 20、40)、右孩子 80(下面挂着 70)。后序遍历也从根 50 出发,但它要「左右子树都处理完才记根」,所以根 50 会是最后一个被记下的。
3. 5进入 值50递归进入节点 值50(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值50,先去把它的左、右子树处理完。
4. 6进入 值30递归进入节点 值30(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值30,先去把它的左、右子树处理完。
5. 7进入 值20递归进入节点 值20(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值20,先去把它的左、右子树处理完。
6. 8记下 值20值20 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20]。
7. 9值20 子树完值20 这棵子树全部遍历完毕,从递归里返回到上一层 值30。
8. 10回到 值30值30 的左子树整段都走完了,递归回到 值30。后序里左边完了还不能记根,先去它的右子树。
9. 11进入 值40递归进入节点 值40(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值40,先去把它的左、右子树处理完。
10. 12记下 值40值40 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20, 40]。
11. 13值40 子树完值40 这棵子树全部遍历完毕,从递归里返回到上一层 值30。
12. 14回到 值30值30 的右子树也走完了,递归回到 值30。左、右子树都处理完了,现在才轮到记根。
13. 15记下 值30值30 的左右子树都遍历完了,这时才把 值30 记进结果(它变绿),现在结果是 [20, 40, 30]。
14. 16值30 子树完值30 这棵子树全部遍历完毕,从递归里返回到上一层 值50。
15. 17回到 值50值50 的左子树整段都走完了,递归回到 值50。后序里左边完了还不能记根,先去它的右子树。
16. 18进入 值80递归进入节点 值80(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值80,先去把它的左、右子树处理完。
17. 19进入 值70递归进入节点 值70(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值70,先去把它的左、右子树处理完。
18. 20记下 值70值70 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20, 40, 30, 70]。
19. 21值70 子树完值70 这棵子树全部遍历完毕,从递归里返回到上一层 值80。
20. 22值80 右空值80 没有右孩子,右子树为空。左、右子树都处理完了,现在才轮到记根。
21. 23记下 值80值80 的左右子树都遍历完了,这时才把 值80 记进结果(它变绿),现在结果是 [20, 40, 30, 70, 80]。
22. 24值80 子树完值80 这棵子树全部遍历完毕,从递归里返回到上一层 值50。
23. 25回到 值50值50 的右子树也走完了,递归回到 值50。左、右子树都处理完了,现在才轮到记根。
24. 26记下 值50值50 的左右子树都遍历完了,这时才把 值50 记进结果(它变绿),现在结果是 [20, 40, 30, 70, 80, 50]。
25. 27值50 子树完值50 是根,它的整棵树都遍历完了,递归回到最外层,后序遍历到此结束。
26. 28遍历完成整棵树后序遍历完成,结果是 20、40、30、70、80、50。回头看:每到一个节点都「先左、再右、最后才记自己」,所以根 50 最后才出现;递归栈帮我们记住回溯路径,每个节点恰好访问一次,所以是 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node):
            if node:
                dfs(node.left); dfs(node.right); ans.append(node.val)
        dfs(root)
        return ans

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: vector<int> postorderTraversal(TreeNode* root){ vector<int> ans; function<void(TreeNode*)> dfs=[&](TreeNode* n){ if(!n) return; dfs(n->left); dfs(n->right); ans.push_back(n->val); }; dfs(root); return ans; } };

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public List<Integer> postorderTraversal(TreeNode root){ ArrayList<Integer> ans=new ArrayList<>(); dfs(root,ans); return ans; } void dfs(TreeNode n,List<Integer> ans){ if(n==null)return; dfs(n.left,ans); dfs(n.right,ans); ans.add(n.val); } }

复杂度

面试官可能追问