leetcode-105-从前序与中序遍历构造二叉树

# 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:
        def helper(in_left=0,in_right=len(inorder)):
            nonlocal pre_idx 
            # if there is no elements to construct subtrees 
            if in_left == in_right: return None 
            # pick up pre_idx element as a root 
            root_val = preorder[pre_idx] 
            root = TreeNode(root_val) 
            # root splits inorder list 
            # into left and right subtrees 
            index = idx_map[root_val] 
            # recursion 
            pre_idx += 1 
            # build left subtree 
            root.left = helper(in_left, index) 
            # build right subtree 
            root.right = helper(index + 1, in_right) 
            return root 
        # start from first preorder element 
        pre_idx = 0 
        # build a hashmap value -> its index 
        idx_map = {val:idx for idx, val in enumerate(inorder)} 
        return helper()