Construct Binary Tree from Preorder and Inorder Traversal
Problem Description
Question
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output:[3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderandinorderconsist of unique values.- Each value of
inorderalso appears inpreorder. preorderis guaranteed to be the preorder traversal of the tree.inorderis guaranteed to be the inorder traversal of the tree.
Solve it on LeetCode
Approaches
1. Recursive Construction (Naive)
Intuition:
The main idea is to understand the properties of preorder and inorder traversal:
- In preorder traversal, the first element is always the root of the tree.
- In inorder traversal, the elements left of the root belong to the left subtree and the elements right of the root belong to the right subtree.
We can recursively construct the tree by following these steps:
- Identify the root from the preorder list.
- Find the index of this root in the inorder list.
- Split the inorder list into left and right subtrees.
- Recursively build the left and right subtrees.
Code:
Complexity Analysis
- Time Complexity: O(N^2), where N is the number of nodes. This is because for each node, we potentially scan the entire inorder array.
- Space Complexity: O(N), for the recursion call stack.
2. Optimized Recursive Construction using HashMap
Intuition:
The inefficiency in the previous approach is due to scanning the inorder array to find the root index. We can use a HashMap to store the index of each value in the inorder array, allowing O(1) lookup for the root index.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes. We avoid repeated scanning of inorder by using HashMap.
- Space Complexity: O(N), for the recursion call stack and the HashMap.