从中序与后序遍历序列构造二叉树 图解题解

这道题到底在问什么

inorder

[9,3,15,20,7]

postorder

[9,15,7,20,3]

输出

[3,9,20,null,null,15,7]

最优解：一步一步想明白

1. 3不能。单看中序 [9,3,15,20,7],你不知道谁是根——树可以有很多种长法,中序结果一样。必须再给一串顺序当「定位器」。
2. 4后序是「左→右→根」,根永远最后访问。所以后序末尾那个数,就是当前这棵(子)树的根。这是第一把钥匙。
3. 5中序是「左→根→右」,所以根在中序里的位置,天然把数组切成两半:左半边是左子树的全部节点,右半边是右子树的全部。这是第二把钥匙。
4. 6盯三样东西:后序从右往左一个个被取走当根、中序区间被根切成左右两段、下方那棵树一格一格长出来。
5. 7postorder 取末尾 → 3先看后序 [9,15,7,20,3]。末尾的 3 是整棵树的根。取走它,后续在剩下的 [9,15,7,20] 里继续找子树的根。
6. 8inorder 里 3 在下标 1拿着根 3 回到中序 [9,3,15,20,7],它在下标 1。它左边 [9](下标 [0,0])是左子树,右边 [15,20,7](下标 [2,4])是右子树。
7. 93 落地,成为树根第一个节点 3 出现,它是整棵树的根。后序的递归约定是先建右子树(因为根从后往前取,右边的根先冒出来),所以下一步先去搭 3 的右子树 [2,4]。
8. 10剩 [9,15,7,20] 取末尾 → 20根 3 取走后,后序还剩 [9,15,7,20]。新的末尾 20 就是 3 右子树的根。后序末尾总是「下一个要挂的根」。
9. 11在右段 [2,4] 里,20 在下标 3在中序的右段 [2,4] 里找 20,它在下标 3。于是 20 把这段切成:左边 [15](下标 [2,2])、右边 [7](下标 [4,4])。左边已用掉的 [9,3] 灰掉了。
10. 1220 → 3 的右孩子20 挂到 3 的右下方。它自己又有左右两段要建,同样先建右 [4,4]、再建左 [2,2]。
11. 13剩 [9,15,7] 取末尾 → 720 取走后,后序剩 [9,15,7],末尾 7。它对应中序右段 [4,4],只有一个数,所以 7 是个叶子。
12. 14区间 [4,4] → 7中序区间缩到只剩 [4,4] 一个数 7。单个元素就是叶子:它左右都空,挂为 20 的右孩子后,这一支就到底了。
13. 157 → 20 的右孩子7 落在 20 的右下角,是片叶子。20 的右边搞定,函数回头处理 20 的左段 [2,2]。
14. 16剩 [9,15] 取末尾 → 157 取走后,后序剩 [9,15],末尾 15。它对应中序左段 [2,2],也只有一个数,又是叶子。
15. 17区间 [2,2] → 15中序区间缩到 [2,2],只剩 15。它挂为 20 的左孩子。到这里 20 的左右孩子都齐了,3 的整棵右子树建完。
16. 1815 → 20 的左孩子15 落在 20 的左下角。根 3 的整棵右子树建好了,函数才回头去建 3 的左段 [0,0]。
17. 19剩 [9] 取末尾 → 9后序只剩最后一个 9,它对应中序左段 [0,0]。这是 3 的左孩子,也是最后一个待安家的数。
18. 20区间 [0,0] → 9中序区间缩到 [0,0],只剩 9。它挂为 3 的左孩子。所有 5 个数都要安家了。
19. 219 → 3 的左孩子9 落在 3 的左下角。后序从右往左一个个取根、中序每次切左右段,5 个数一格一格全长进了树里。
20. 22还原成功 [3,9,20,null,null,15,7]树还原完成:根 3,左孩子 9,右孩子 20;20 再带 15 和 7。和题目给的标准输出 [3,9,20,null,null,15,7] 完全一致。
21. 23左→根→右,先走最左:9先按「左→根→右」验一遍。一路往左走到底,最先访问最左的 9。中序结果应当和原 inorder 一字不差。
22. 24回到根:39 没有孩子,回到它的父节点、也是整棵树的根 3。已亮的 9 变灰,当前点亮 3。接着去走 3 的右子树。
23. 25进右子树最左:15进入右子树,先走到它的最左 15(20 的左孩子)。到这里序列是 9 → 3 → 15,和原 inorder 前三个对得上。
24. 2615 的父:20,再到 7再访问 15 的父 20、最后它的右孩子 7。完整中序 9 → 3 → 15 → 20 → 7,和原 inorder 分毫不差。
25. 27左→右→根:9,15,7,20,3再按「左→右→根」走一遍:9 → 15 → 7 → 20 → 3,正好等于原后序数组。两种遍历都对上,说明我们建的树分毫不差。
26. 28因为每次都从后序末尾弹一个数当根,而末尾紧挨着的是「右子树的根」。要让弹出的顺序对上,代码里就得先 build(右) 再 build(左)。顺序反了,树就会错。
27. 31凡是「给两种遍历还原树」的题(LC105 前序+中序、本题后序+中序)都是这一招:一种序列提供根,中序提供左右边界。想通这点,这一类题就全通了。
28. 33先建左 → 弹错根 → 树全错若代码先 build(左),会把本该当右孩子的 20 错挂成左孩子,9、20 左右颠倒,整棵树全错。后序题必须先右后左。

⚠️ 容易写错的地方

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

class Solution:
    def buildTree(self, inorder, postorder):
        idx = {v: i for i, v in enumerate(inorder)}  # 值→中序下标
        def build(lo, hi):
            if lo > hi:                 # 中序区间为空 → 无节点
                return None
            val = postorder.pop()       # 后序末尾 = 当前根
            root = TreeNode(val)
            mid = idx[val]              # 根在中序里的位置
            root.right = build(mid + 1, hi)  # 先建右子树
            root.left  = build(lo, mid - 1)  # 再建左子树
            return root
        return build(0, len(inorder) - 1)

class Solution {
public:
    unordered_map<int,int> idx;
    vector<int> post;
    int pos;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        post = postorder; pos = (int)post.size() - 1;
        for (int i = 0; i < (int)inorder.size(); i++) idx[inorder[i]] = i;
        return build(0, (int)inorder.size() - 1);
    }
    TreeNode* build(int lo, int hi) {
        if (lo > hi) return nullptr;            // 空区间
        int val = post[pos--];                  // 后序末尾 = 根
        TreeNode* root = new TreeNode(val);
        int mid = idx[val];                     // 中序定位
        root->right = build(mid + 1, hi);       // 先右
        root->left  = build(lo, mid - 1);       // 再左
        return root;
    }
};

class Solution {
    private Map<Integer,Integer> idx = new HashMap<>();
    private int[] post;
    private int pos;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.post = postorder;
        this.pos = postorder.length - 1;
        for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
        return build(0, inorder.length - 1);
    }
    private TreeNode build(int lo, int hi) {
        if (lo > hi) return null;               // 空区间
        int val = post[pos--];                  // 后序末尾 = 根
        TreeNode root = new TreeNode(val);
        int mid = idx.get(val);                 // 中序定位
        root.right = build(mid + 1, hi);        // 先右
        root.left  = build(lo, mid - 1);        // 再左
        return root;
    }
}

复杂度

面试官可能追问