Construct Binary Tree From Preorder and Inorder Traversal
- 2 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- We need to notice that the first node in a preorder list is always the root
- We can use recursion to our advantage here:
- First, get the base case out of the way, if either preorder or inorder is null, return None. We will be passing slices of arrays to deeper recursion calls, and because we're indexing them, they will eventually become null at a point
- After creating the root node, check the index of this value in the inorder list. This index is called mid
- In preorder, everything from index 1 to mid + 1 will be in the left child of the current node. For the right child, all elements from mid + 1 to end
- From this point, to figure out which of the remaining nodes in the preorder (starting from index 1) go to the right and left childs respectively, we can use the inorder array.
- Conveniently for us, everything to the left of the current root's value in inorder will be the left child, and everything to the right will be the right chiod
- Intuitively, this makes no sense. So in an interview, draw up the individual preorder and preorder arrays, and figure out the indexing yourself.
- This problem is stupid.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid + 1])
root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
return root