题解 | 重建二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param preOrder int整型一维数组 
# @param vinOrder int整型一维数组 
# @return TreeNode类
#

"""
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/636827642/


"""
class Solution:
    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        # write code here
        # 存储所有的中序遍历的节点
        map=dict()
        for i in range(len(vinOrder)):
            map[vinOrder[i]]=i
        
        # 递归辅助函数
        def buildhelp(preorder,preleft,preright,inorder,inleft,inright):
            if preleft>preright:
                return 
            # 前序遍历的第一个节点就是根节点位置
            preorder_root=preleft
            # 获取中序中根节点位置
            inorder_root=map[preorder[preorder_root]]
            # 创建根节点 
            root= TreeNode(preorder[preorder_root])
            #递归左子树
            root.left=buildhelp(preorder,preleft+1,inorder_root-inleft+preleft,inorder ,inleft,inorder_root-1) 
            root.right=buildhelp(preorder,inorder_root-inleft+preleft+1,preright,inorder,inorder_root+1,inright)
            return root
        root =buildhelp(preOrder,0,len(preOrder)-1,vinOrder,0,len(vinOrder)-1)
        return root