【LeetCode】105. Constructing binary trees from preorder and inorder traversal sequences

0. summary

• Blog source ： [email protected]

---

1. subject

Construct a binary tree according to preorder traversal and inorder traversal .

2. thought

Key code ：
left_num = bound - in_left # You need to find the number of nodes on the left subtree
Because the left subtree also has a number , Therefore, it is required to pass the update parameters , The number of nodes in the left subtree should be taken into account , The same is true for right subtrees .

3. Code

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        root = self.dfs(preorder,inorder,0,len(preorder)-1,0,len(inorder)-1)
        return root

    def dfs(self,preorder,inorder,pre_left,pre_right,in_left,in_right):
        if pre_left > pre_right:
            return None
        # if pre_left == pre_right: #  Only one node , Go straight back to 
        # return TreeNode(preorder[pre_left])
        
        #  Build up trees , The root node of the current tree 
        root_val = preorder[pre_left]
        cur_root = TreeNode(root_val)
        
        new_pre_left = pre_left + 1
        new_pre_right = pre_right

        #  Find the left and right sides , Then build a tree separately 
        bound = inorder.index(root_val)        
        new_in_right = bound - 1       

        #  You need to find the number of nodes on the left subtree 
        left_num = bound - in_left

        #  What is passed in here is still a complete array 
        #  Build a left subtree 
        left = self.dfs(preorder,inorder,pre_left+1,pre_left+left_num,in_left,bound-1)
        
        #  Build right subtree 
        right = self.dfs(preorder,inorder,pre_left+left_num+1,pre_right,bound+1,in_right)

        cur_root.left = left
        cur_root.right = right
        return cur_root