Construct Binary Tree from Preorder and Inorder Traversal
leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
Introduction
Use a breif example to talk though preorder, inorder and postorder traversal of a binary tree:
For a Binary Tree looks like this:
+
/ \
1 2
-Traverse-
Preorder: +12 (node to left to right)
Inorder: 1+2 (left to node to right)
Postorder: 12+ (left to right to node)Hash Map
TIP
If we want to use dfs, we discover we can actually splits it by its root node, split it as node->left and node->right.
- We use hash map to store value to its indexes.
- apply dfs algorithm
- with
left side for inorder is i to mid-1, while mid is the root node.
cpp
unordered_map<int, int>mp;
int idx = 0;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0; i < preorder.size(); i++)
mp[inorder[i]] = i;
return build(preorder, 0, inorder.size()-1);
}
TreeNode* build(vector<int>& preorder, int i, int j) {
if(i <= j) {
auto it = new TreeNode(preorder[idx++]);
int mid = mp[it->val];
it->left = build(preorder, i, mid-1); // left side for inorder is i to mid-1
it->right = build(preorder, mid+1, j);
return it;
}
return nullptr;
}Without Hashmap
Technically faster, but theoretically, the Time complexity is both O(n).
cpp
unordered_map<int, int>mp;
int idx = 0;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, inorder.size()-1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int i, int j) {
if(i <= j) {
auto it = new TreeNode(preorder[idx++]);
int mid = i;
while(inorder[mid] != it->val) mid++;
it->left = build(preorder, inorder, i, mid-1);
it->right = build(preorder, inorder, mid+1, j);
return it;
}
return nullptr;
}