Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]
Output: [-1]

• This question can be solved by Depth First Search.

• This question is good one, it takes a special way to test the concept of tree traversal and also help you have deeper understand of tree traversal.

• Before we do the question, we should have some knowledge about Preorder, Inoreder and Postorder in advanced.

• Suppose we have three results array from binary tree traversal and they are Preorder, Inorder and Postorder. What we get from these informations?

• The first node of Preorder and the last node of the Postorder are both the root node of the binary tree.

• If we know the root node, then from Inorder, we know that the left side of the root node will build left subtree and rigth side of root node will build right subtree.

• We know the result of Preorder is listed in [root, left, right] order

• We know the result of Postorder is listed in [left, right, root] order

• From all the information above we can apply dfs to build the binary tree by using Preorder and Inorder or Postorder and Inorder.

• To sum up, we need Preorder or Postorder to locate the root node, and we need Inorder to divide left subtree and right subtree nodes.

• Ok, for this question,

• We first get root node from Preorder

• Then we get the root node index from Inorder, now we know the amount of left subtree nodes and the amount of right subtree nodes. we also find the left part and right part of the inorder.

• Since we knwo both the amount of the left subtree node and right subtree nodes and we know Preorder is in this format [root,left,right], we will find the preorder of left part and right part.

• We recursively apply the new preorder list and inorder list to the function.

# 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:
            if not preorder or not inorder:
                return None
            root = TreeNode(preorder[0])
            preorder_left_node_amount = inorder_root_index = inorder.index(preorder[0])
            root.left = self.buildTree(preorder[1:preorder_left_node_amount+1], inorder[:inorder_root_index])
            root.right = self.buildTree(preorder[preorder_left_node_amount+1:],inorder[inorder_root_index+1:])
            return root