经典面试题，考察对树的中序、前序、后续遍历的理解以及递归算法的运用。

Tag

树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出：

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

限制：0 <= 节点个数 <= 5000

直觉

前序遍历 preorder = [3,9,20,15,7] 根 左 右 中序遍历 inorder = [9,3,15,20,7] 左 根 右 3 为根节点，[9]为第二层左子树，[15,20,7]为第二层右子树。

1. 根据前序遍历结果得到根节点。
2. 再利用根节点在中序遍历中的位置，分割中序遍历结果，得到左右子树。
3. 接着递归调用recur处理左右子树。

代码

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        self.dic, self.po = {}, preorder  # 注意这种self成员变量的声明和使用方法
        for i in range(len(inorder)):
            self.dic[inorder[i]] = i
        return self.recur(0, 0, len(inorder)-1)
    
    def recur(self, pre_root, in_left, in_right):
        if in_left > in_right: return
        # 1. 根据前序遍历结果得到根节点。
        root_node = TreeNode(self.po[pre_root])
        # 2. 再利用根节点在中序遍历中的位置，分割中序遍历结果，得到左右子树。
        index = self.dic[self.po[pre_root]]
        # 3. 接着递归调用recur处理左右子树。
        root_node.left = self.recur(pre_root + 1, in_left, index - 1)
        root_node.right = self.recur(index - in_left + pre_root + 1, index + 1, in_right)
        return root_node