Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal (Python)

Related Topic

Depth-First-Search. Tree. Preorder-Traversal. Inorder-Traversal.

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Sample I/O

For example, given

Example 1

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Methodology

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?

1. The first node of Preorder and the last node of the Postorder are both the root node of the binary tree.
2. 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.
3. We know the result of Preorder is listed in [root, left, right] order
4. 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,

1. We first get root node from Preorder
2. 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.
3. 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.
4. We recursively apply the new preorder list and inorder list to the function.

Code

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

BigO

We go through both preorder list and inorder list, so the total time complexity is O(2n)