105. 从前序与中序遍历结果构造二叉树

当我们遍历一棵二叉树的时候，根据遍历根节点的顺序的不同，可以有三种方法，前序遍历（Preorder），中序遍历（Inorder），后序遍历（Postorder）。分别对应着先访问根节点，在先左子树，然后访问根节点，接着右子树，或者最后访问根节点。这是很基本的数据结构知识点。今天的题目就是，给定一个二叉树的前序遍历和中序遍历结果，根据这个还原出二叉树。

其实前序遍历加中序遍历结果，就会唯一确定一棵二叉树。现在无非怎么操作的问题。我们可以从一个实例来分析这个：

1
2

preorder = [1, 2, 3, 4, 5, 6, 7, 8, 9]
inorder  = [3, 2, 4, 1, 6, 5, 8, 7, 9]

前序遍历的第一个节点是 1，则，在中序遍历中 3，2，4，[1]，6，5，8，7，9，就把序列分成了两份，前半段是左子树，后半段就是右子树。前序遍历的第二个节点是 2，则中序中的前半段 3，[2]，4，通过 2 把它又分成了两段，3，就是左子树，4，就是右子树。正好对应着前序遍历的第三个节点和第四个节点……

从这个顺序里，我们可以发现，前序遍历序列，我们只要按顺序逐个处理，而中序遍历的，我们不断分割左右两半，然后就是递归地处理这个过程。基于这个原理，我们可以用 Python 很简洁地写出这个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        n = len(preorder)
        pre = iter(preorder)

        def rec(left: int, right: int) -> TreeNode:
            if left >= right:
                return None
            r = next(pre)
            m = inorder.index(r, left, right)
            ltree = rec(left, m)
            rtree = rec(m + 1, right)
            return TreeNode(r, ltree, rtree)

        return rec(0, n)

我们声明一个函数 rec，代表 reconstruction（重建），用下标 left 和 right 来标记中序遍历序列的下标。因为前序遍历序列的分析，就是按顺序，所以我们生成一个迭代器来操作它，而下标 left 和 right，作用就是探测已到达叶子节点的标记。因为 index 这个方法的搜索范围是左闭右开区间的，所以我们对 left 和 right 的取值控制也是左闭右开的，这点需要注意。（为什么递归终止条件是 left >= right，因为是左闭右开，一个有效区间必须满足 left < right，区间里面才会有元素。）

看这个递归体里，我们用迭代器访问前序遍历的序列，迭代器不断往前移动，刚好把每个元素都访问了一遍。所以，整个算法的时间复杂度是 O(n)。