面试题07. 重建二叉树

题目描述

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3

/ \
9 20
/ \
15 7

解题思路

分治递归。突破点在于找到前序遍历与中序遍历的关系。

1. 前序遍历的第一个元素一定是根节点
2. 中序遍历中，根节点左边为左子树，右边为右子树
   按照这个思路，通过前序遍历找到的根节点，确定中序遍历中根节点的位置，从而确定左子树的个数。
   通过左子树的个数，可以在前序遍历找到左子树的前序遍历，右子树同样如此，这样就找到了分治递归的方向

代码

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return 
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        root = TreeNode(preorder[0])
        for i in range(len(inorder)):
            if inorder[i] == preorder[0]:
                root.left = self.buildTree(preorder[1:1+i], inorder[:i])
                root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
                break
        return root