题解 | #重建二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param preOrder int整型一维数组 
# @param vinOrder int整型一维数组 
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        # write code here
        if not preOrder:
            return None
        
        pos = dict()
        for i in range(len(vinOrder)):
            pos[vinOrder[i]] = i
        
        self.preOrder = preOrder
        self.pos = pos

        return self.dfs(0, len(preOrder)-1, 0, len(vinOrder))
    
    def dfs(self, pl, pr, il, ir):
        if pl > pr:
            return None
        
        root = TreeNode(self.preOrder[pl])
        p = self.pos[self.preOrder[pl]]
        root.left = self.dfs(pl+1, pl+p-il, il, p-1)
        root.right = self.dfs(pl+p-il+1, pr, p+1, ir)

        return root