[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

 

 

Problem

 

 

---

 

Solution

 

First element of preorder will always be the root of the tree.

Inorder traversal searches left tree and then right tree, so we can find the root element in the list and divide the list up into left and right side(trees). Now we can build those trees.

Repeat this process with the root of left tree, which is the second element in the preorder list. Then use the third element as the root of the right tree.

 

Time Complexity

O(M) where M is the number of nodes in the tree

 

 

Space Complexity

O(N)

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None
        rootInd = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[rootInd])
        root.left = self.buildTree(preorder, inorder[:rootInd])
        root.right = self.buildTree(preorder, inorder[rootInd+1:])
        return root