reconstruct binary tree 类型的题目general 的思路：
利用递归的思想，在每次确定root之后，分别找出该root对应的left subtree 和right subtree的序列，可以用两个vector分别保存这两个序列，也可以利用在原来序列的边界index来表示着两个序列。
Q1: Reconstruct Binary Tree With Preorder And Inorder
preorder traversal = {5, 3, 1, 4, 8, 11}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
5
/ \
3 8
/ \ \
1 4 11
analysis:
Preorder traversal of a tree: root-> left-subtree -> right-subtree
Inorder traversal of a tree: left-subtree -> root -> right-subtree
From preorder traversal, we can get the root of the tree. With the root of the tree, in inorder traversal, we can get the left subtree and right subtree. If we know the number of left subtree, we can get the preorder tranversal of left subtree preorder traversal vector; the same as the right subtree.
To find the root index in inorder traversal quickly, we can use a hashmap to store the element and its index in inorder traversal.
Recursion can be used in this problem
Solution:
//class TreeNode {
// public:
// int value;
// TreeNode* left;
// TreeNode* right;
// TreeNode(int v) : value(v), left(NULL), right(NULL) {}
//};
class Solution {
private:
void helper(TreeNode* &root, vector<int> in, vector<int> pre, int ileft, int iright, int pleft, int pright, map<int, int> inmap) {
//base case
//to check if it needs to return if ileft == iright, we can just use a simple case when there is only one node in the tree, ileft == iright, can't return NULL;
if (ileft > iright || pleft > pright) return;
//recursion rule
//step1: find root index in inorder
root = new TreeNode(pre[pleft]);
int rootI = pre[pleft];
int rin = inmap[rootI];
//step2: construct left subtree
int left_size = rin - ileft;
// int right_size = iright - rin;
helper(root->left, in, pre, ileft, ileft+left_size-1, pleft+1, pleft+left_size, inmap);
//step3: construct right subtree
helper(root->right, in, pre, rin+1, iright, pleft+left_size+1, pright, inmap);
}
public:
TreeNode* reconstruct(vector<int> in, vector<int> pre) {
TreeNode* root = NULL;
//sanitary check
if (in.size() == 0 || pre.size() == 0) return root;
//use hashmap to store the element and its index in inorder tranversal
map<int, int> inmap;//key: element value: index
for (int i = 0; i < in.size(); i++) {
inmap[in[i]] = i;
}
helper(root, in, pre, 0, in.size()-1, 0, pre.size()-1, inmap);
return root;
}
};
Time complexity: traverse the inorder and preorder vector once
O(n)
Space complexity: O(n) -> construct the tree
Q2: Reconstruct Binary Tree With Postorder And Inorder
postorder traversal = {1, 4, 3, 11, 8, 5}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
5
/ \
3 8
/ \ \
1 4 11
analysis:
postorder traversal: left-subtree -> right-subtree->root
inorder traversal: left-subtree-> root -> right-subtree
From postorder traversal, we can get the root from the last element in the vector, with the root we can get the left-subtree and right-subtree from the inorder traversal, same as previous question.
Solution:
class Solution {
private:
void helper(TreeNode* &root, vector<int> in, vector<int> post, int ileft, int iright, int pleft, int pright, map<int, int> inmap) {
//base case
if (ileft > iright || pleft > pright) return;
//get root index in in
int rooti = post[pright];
root = new TreeNode(rooti);
int rI = inmap[rooti];
int left_size = rI-ileft;
helper(root->left, in, post, ileft, ileft+left_size-1, pleft, pleft+ left_size-1, inmap);
helper(root->right, in, post, rI+1, iright, pleft+left_size, pright-1, inmap);
}
public:
TreeNode* reconstruct(vector<int> in, vector<int> post) {
//sanitary check
if (in.size() == 0 || post.size() == 0) return NULL;
TreeNode* root;
map<int, int> inmap;
for (int i = 0; i < in.size(); i++) {
inmap[in[i]] = i;
}
helper(root, in, post, 0, in.size()-1, 0, post.size()-1, inmap);
return root;
}
};
Time complexity: O(n);
Space complexity: O(n);
Q3: Reconstruct Binary Tree With Levelorder And Inorder
levelorder traversal = {5, 3, 8, 1, 4, 11}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
5
/ \
3 8
/ \ \
1 4 11
Analysis:
we can find the root node in level order, which is the first element. With the root node, we will get the elements in left subtree and right subtree from inorder. Then we have to find elements in left subtree and right subtree in level traversal. How to find elements in level traversal? for each elements in level order, if the index of this element in inorder traversal is smaller than the root index, then it is in left subtree, otherwise it is in right subtree. Given the left subtree and right subtree in inorder traversal and level traversal, we can reconstruct the tree recursively.
class Solution {
private:
void helper(TreeNode* &rst, vector<int> level,map<int, int> inmap) {
//base case
if (level.empty()) return;
vector<int> left;
vector<int> right;
//find the root in inorder
int root = level[0];
rst = new TreeNode(root);
int ridx = inmap[root];
for (int i = 0; i < level.size(); i++) {
if (inmap[level[i]] <= ridx-1 ) {
left.push_back(level[i]);
}else if (inmap[level[i]] >= ridx+1) {
right.push_back(level[i]);
}
}
helper(rst->left, left, inmap);
helper(rst->right, right, inmap);
}
public:
TreeNode* reconstruct(vector<int> in, vector<int> level) {
//sanity check
if (in.size() == 0 || level.size() == 0) return NULL;
map<int, int> inmap;
for (int i = 0; i < in.size(); i++) {
inmap[in[i]] = i;
}
TreeNode* rst;
helper(rst, level, inmap);
return rst;
}
};
Time complexity: O(n)
space complexity: O(n)
Q4: Reconstruct Binary Search Tree With Preorder Traversal
analysis:
Binary search tree's property: for every root node, the elements in left subtree are smaller than the root node value, the elments in right subtree are larger than the root node value. How to construct the left subtree and right subtree of each root node? find all elements that is smaller than the root node in preorder traversal and all elements that is larger than the root node in preoder traversal. With these information, we can construct the binary search tree recursively.
class Solution {
private:
void helper(vector<int> pre, TreeNode* &rst, int left, int right) {
//base case
if (left > right) return;
rst = new TreeNode(pre[left]);
//find the boundary of left subtree and right subtree
int i = 0;
for (i = left; i <= right; i++) {
if (pre[i] > pre[left]) break;
}
helper(pre, rst->left, left+1, i-1);
helper(pre, rst->right, i ,right);
}
public:
TreeNode* reconstruct(vector<int> pre) {
//sanitary check
if (pre.size() == 0) return NULL;
TreeNode* rst;
helper(pre, rst, 0, pre.size()-1);
return rst;
}
};
Time complexity: O(n);
Space complexity: O(1);
Q5: Reconstruct Binary Search Tree With Postorder Traversal
analysis:
The same theory as the previous one except the root is the rightmost element in post order traversal.
class Solution {
private:
void helper(vector<int> post, TreeNode* &rst, int left, int right) {
//base case
if (left > right) return;
rst = new TreeNode(post[right]);
int i = 0;
for (i = right-1; i >= 0; i--) {
if (post[i] < post[right]) break;
}
helper(post, rst->left, left, i);
helper(post, rst->right, i+1, right-1);
}
public:
TreeNode* reconstruct(vector<int> post) {
//sanity check
if (post.size() == 0) return NULL;
TreeNode* rst;
helper(post, rst, 0, post.size()-1);
return rst;
}
};
Time complexity: O(n)
space complexity: O(1)
Q6: Reconstruct Binary Search Tree With Level Order Traversal
analysis:
find the left subtree and right subtree in level order traversal by iterating the level order vector to find the elements smaller than the root node and the elements larger than the root node.
class Solution {
private:
void helper(TreeNode* &rst, vector<int> level) {
//base case
if (level.empty()) return;
int root = level[0];
rst = new TreeNode(root);
vector<int> left;
vector<int> right;
for (int i = 1; i < level.size(); i++) {
if (level[i] < root) left.push_back(level[i]);
if (level[i] > root) right.push_back(level[i]);
}
helper(rst->left, left);
helper(rst->right, right);
}
public:
TreeNode* reconstruct(vector<int> level) {
//sanity check
if (level.size() == 0) return NULL;
TreeNode* rst;
helper(rst, level);
return rst;
}
};
time complexity: O(n);
space complexity: O(1);
No comments:
Post a Comment