题解 | #重建二叉树#

# 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
        idx = [0]*(20002)
        for i, n in enumerate(vinOrder): idx[n] = i

        ii = 0
        def build_tree(s, e):
            nonlocal ii
            print(s, e, ii)
            if s >= e: return None
            n = preOrder[ii]
            ii+=1
            p = idx[n]
            node = TreeNode(n)
            node.left = build_tree(s, p)
            node.right = build_tree(p+1, e)
            return node
        
        tree = build_tree(0, len(preOrder))
        print(tree)
        return tree