MediumNeetCode150ArrayHash TableDivide and ConquerTreeBinary Tree
Construct Binary Tree from Preorder and Inorder Traversal
Construct binary tree from preorder and inorder.
Examples
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
Constructed tree.
Constraints
- •
1 <= preorder.length <= 3000 - •
inorder.length == preorder.length - •
-3000 <= Node.val <= 3000 - •
All values unique
Approaches
Index search in inorder.
CodeT: O(n^2) | S: O(n)
def buildTree(pre, inorder):
if not pre or not inorder: return None
root=TreeNode(pre[0])
mid=inorder.index(pre[0])
root.left=buildTree(pre[1:mid+1],inorder[:mid])
root.right=buildTree(pre[mid+1:],inorder[mid+1:])
return rootO(1) index lookup.
CodeT: O(n) | S: O(n)
def buildTree(pre, inorder):
m={v:i for i,v in enumerate(inorder)}
def h(pi,pe,ii,ie):
if pi>pe: return None
root=TreeNode(pre[pi]); mid=m[pre[pi]]; ls=mid-ii
root.left=h(pi+1,pi+ls,ii,mid-1)
root.right=h(pi+ls+1,pe,mid+1,ie)
return root
return h(0,len(pre)-1,0,len(inorder)-1)Avoid slicing.
CodeT: O(n) | S: O(n)
def buildTree(pre, inorder):
m={v:i for i,v in enumerate(inorder)}; pi=[0]
def dfs(is_,ie):
if is_>ie: return None
rv=pre[pi[0]]; pi[0]+=1; root=TreeNode(rv)
mid=m[rv]
root.left=dfs(is_,mid-1); root.right=dfs(mid+1,ie)
return root
return dfs(0,len(inorder)-1)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursive Linear Search | O(n^2) | O(n) | Index search in inorder. |
| Recursive with HashMap | O(n) | O(n) | O(1) index lookup. |
| Recursive Optimized | O(n) | O(n) | Avoid slicing. |
Recursive Linear Search
T: O(n^2)S: O(n)
Index search in inorder.
Recursive with HashMap
T: O(n)S: O(n)
O(1) index lookup.
Recursive Optimized
T: O(n)S: O(n)
Avoid slicing.
Common Mistakes
Wrong index mapping
Off-by-one in slicing
Forgetting preorder gives root first