【剑指offer】面试题07. 重建二叉树

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

例如，给出

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

3

/
9 20
/
15 7

限制：

0 <= 节点个数 <= 5000

# 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:
        '''
        前序遍历的第一个值为根结点，则根据此节点在中序遍历的位置可分成左子树和右子树，
        进而又可以根据左子树和右子树的长度实现对前序遍历的划分，形成递归求解
        '''
        maps = {num:index for index,num in enumerate(inorder)}
        def helper(l1,r1,l2,r2):
            # l1,r1分别为当前处理 preorder的左右边界，l2,r2 分别为当前处理 inorder 的左右边界
            if l1 > r1:return None 
            root = TreeNode(preorder[l1])
            pivot = maps[preorder[l1]]
            root.left = helper(l1 + 1,l1 + pivot - l2,l2,pivot + 1)
            root.right = helper(l1 + pivot - l2 + 1,r1,pivot + 1,r2)

            return root
        return helper(0,len(preorder) - 1,0 ,len(inorder) - 1) if preorder else None