LC105　从前序与中序遍历序列构造二叉树¶

中等通过率 73.3%python3核心代码模式二叉树样例通过牛客 AC树数组哈希表分治二叉树

一句话

前序给出根，中序按根切成左右两段，逐层分解。

解题思路¶

这题考什么¶

两条序列各自都不足以确定一棵树，合起来才行（前提是元素互不重复，题面已保证）：

前序 = [根] + 前序(左子树) + 前序(右子树)
中序 = 中序(左子树) + [根] + 中序(右子树)

由此得到唯一的分解路径：前序的第一个元素必是当前子树的根；到中序里找到这个值的位置 mid，它左边的一段就是左子树的全部节点，右边的一段就是右子树的全部节点。两段的长度一确定，前序里对应的两段也随之确定。重建二叉树的原理见树的基础与遍历的「二叉树的三种遍历」一节。

实现上还有个更省事的观察：前序里节点出现的顺序，恰好就是深度优先地「先建根、再建整棵左子树、最后建整棵右子树」的顺序。所以只要保证处理顺序是这个顺序，就可以用一个只增不减的游标顺次取根，完全不必去算「左子树在前序里占了哪一段」。这里用显式栈维持这个顺序：弹出一个待建区间就消费一个前序元素，压栈时先压右段后压左段，弹出时左段先到手。

示例 1：preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]。

取 3 当根，它在中序的下标是 1
    -> 左段是 inorder[0..0]，右段是 inorder[2..4]
建左段：取 9 当根，中序区间只剩它自己，两侧都是空区间
建右段：取 20 当根，它在中序的下标是 3 -> 左段 [15]、右段 [7]
依次取 15、7 建成两个叶子

得到 [3,9,20,null,null,15,7]，与样例一致。

数据规模与复杂度¶

1 <= preorder.length <= 3000，两数组等长，值域 [-3000, 3000] 且无重复元素。中序下标先预处理成「值 -> 下标」的哈希表，建每个节点时定位根是 O(1)，总时间 O(n)；若每次都用 inorder.index(val) 现找，单次 O(n)，链状树下总量退化成 3000 * 3000 = 9 * 10^6 次比较，这个规模还扛得住，但一旦上界再抬一档就没救，哈希表是这里唯一值得写的优化。空间 O(n)：哈希表 n 项，栈深不超过树高。

坑在哪¶

必须用显式栈。n 到 3000，退化成一条链时递归深度就是 3000，超过 CPython 默认的 1000 层上限，递归版会 RecursionError；递归改迭代见 DFS 深度优先搜索的 60.4 节。
压栈顺序是先右后左。栈是后进先出，写反了就会先建右子树，而游标此刻取到的却是左子树的根，整棵树的形状全错。
空区间也要压栈、弹出后再跳过，且跳过时不能动游标。空子树在前序里不占任何元素，误消费一个就等于把兄弟子树的根偷走了。
哈希表记的是中序下标。切分左右两段靠的是根在中序里的位置，记成前序下标整个分解就失去意义。
值互不重复是题面给的前提，哈希表才能做到「值 -> 唯一下标」。若允许重复，前序加中序不再唯一确定一棵树，这题的解法整个不成立。

参考实现¶

solutions/leetcode/LC105/sol.py
from typing import List, Optional


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> "Optional[TreeNode]":
        # 题面保证长度 >= 1；空输入按空树处理，省得下面对空列表取首元素
        if not preorder:
            return None
        # 值 -> 它在中序里的下标。切分左右子树只需要这一张表，查一次 O(1)
        pos = {v: i for i, v in enumerate(inorder)}
        # 前序游标只增不减：栈保证了处理顺序就是「根、整棵左子树、整棵右子树」，
        # 那正是前序本身的顺序，所以顺次取值即可
        idx = 0
        root = None
        # 栈元素是 (中序区间左端, 中序区间右端, 父节点, 是否挂在父节点的左边)。
        # 根没有父节点，用 None 占位；区间是闭区间
        stack = [(0, len(inorder) - 1, None, False)]
        while stack:
            lo, hi, parent, is_left = stack.pop()
            # 空区间代表空子树：它在前序里不占元素，所以直接跳过，游标不动
            if lo > hi:
                continue
            # 当前子树的根就是前序游标处的值，取完游标前进一格
            node = TreeNode(preorder[idx])
            idx += 1
            # 把新节点挂到父节点上；根节点单独记下来当返回值
            if parent is None:
                root = node
            elif is_left:
                parent.left = node
            else:
                parent.right = node
            # 根在中序里的位置把区间切成两段：左边全是左子树，右边全是右子树
            mid = pos[node.val]
            # 先压右段、后压左段 —— 栈后进先出，弹出时左段先到手，
            # 与前序里「左子树整段排在右子树之前」的顺序对齐
            stack.append((mid + 1, hi, node, False))
            stack.append((lo, mid - 1, node, True))
        return root

LC105 从前序与中序遍历序列构造二叉树¶