For example:
Given the following binary tree,
1 <--- / \ 2 3 <--- \ \ 5 4 <---You should return
[1, 3, 4].BFS 遍历tree的变形。！！！
这个题目是求从右边往左边看的树上的值，其实如果知道这一题其实是BFSlevel order traverse tree，每次取每一层的最后那个node的话就是从右往左看树的结果， 所以这一题我是用bfs 取每层的最后那个值。
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> rst;
//sanity check
if (root == NULL) return rst;
queue<TreeNode*> explore;
explore.push(root);
while (!explore.empty()) {
int size = explore.size();
for (int i = 0; i < size; i++) {
TreeNode* tmp = explore.front();
if ( i == size-1) rst.push_back(tmp->val);
explore.pop();
if (tmp->left) explore.push(tmp->left);
if (tmp->right) explore.push(tmp->right);
}
}
return rst;
}
};
Extends：
1. print binary tree in vertical order
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9
这个题目一开始看起来没有什么思路，在同一个vertical上的node感觉也没有规律，不知道怎么
标示两个Node是不是在一个vertical上，后来看了网上别人的分析才明白原来两个Node在同一个
vertical上意味着它们离某个原点（root）的距离是相同的，所以这题就转化为先求出tree上面
每个node离root的horizonal distance是多少。 最后输出的就是从最小的distance到最大的
distance每个distance上的node，在求distance的时候用一个Map存起来就可以了。
那么怎么求每个node的distance呢？从原点出发，原点的horizontal distance是0，对于每一个
parentNode而言，向左走，distance = parentNode -1, 向右走 ， distance = parentNode + 1
很显然用recursion的方法preorder traverse tree就可以做了。
class Solution {
public:
//get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, map<int, vector<int>> &tmap, int hd) {
//base case
if (root == NULL) return;
tmap[hd].push_back(root->val);
preorder(root->left, tmap, hd-1);
preorder(root->right, tmap, hd+1);
}
vector<vector<int>> TopView(TreeNode* root) {
vector<vector<int>> rst;
//sanity check
if (root == NULL) return rst;
map<int, vector<int>> tmap;
//count the distance
preorder(root, tmap, 0);
//get the vector
map<int,vector<int>> :: iterator it = tmap.begin();
for (; it != tmap.end(); it++) {
vector<int> tmp;
for (int i = 0; i < (it->second).size(); i++) {
tmp.push_back((it->second)[i]);
}
rst.push_back(tmp);
}
return rst;
}
};
AS the map is implemented by BST, the insert, find and delete operation is all O(logn),
so the time complexity is O(nlogn)
2. view the tree from top to down
1
/ \
2 3
/ \ / \
4 5 6 7
Top view of the above binary tree is
4 2 1 3 7
1
/ \
2 3
\
4
\
5
\
6
Top view of the above binary tree is
2 1 3 6
由于有上面那个vertical view of a tree的基础，这个题目就很简单了，只要在上面的那个解法里面对map的操作进行处理，只记录某个hd第一次出现的node， 就是在map里面存node之前进行判断，看是否已经有node存在里面了，如果已经有node存在里面了，那么就不继续存，
class Solution {
public:
//get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, map<int, vector<int>> &tmap, int hd) {
//base case
if (root == NULL) return;
if (tmap.find(hd) == tmap.end()) {
tmap[hd].push_back(root->val);
cout<< root->val;
}
preorder(root->left, tmap, hd-1);
preorder(root->right, tmap, hd+1);
}
int TopView(TreeNode* root) {
vector<vector<int>> rst;
//sanity check
if (root == NULL) return rst;
map<int, vector<int>> tmap;
//count the distance
preorder(root, tmap, 0);
//get the vector
map<int,vector<int>> :: iterator it = tmap.begin();
return 0 ;
}
};
但是上面的方法由于用了map，所以time complexity 是O(nlogn)
有没有什么方法可以使得时间复杂度降到O(n)呢？
考虑到其实map里面每次都只允许存储一个Node，所以 此时的map相当是当做set来用， 所以如果可以
用hash_set来做的话，时间复杂度是O（1）的查找。但是如何记录哪个node和它的hd的对应关系呢？？
为了解决这个问题，我们可以用object来进行存储，每个object里面存储两个变量，一个node,一个hd。
C++里面的unordered_set和unordered_map就是对应java里面hash_set, hash_map， unordered_set的
对某个特定Key的查找效率比一般的set快很多， 但是unordered_set里面是不能进行排序的。
class Solution {
public://get the horizontal distance of nodes in the tree
void preorder(TreeNode* root, unordered_set<int> &uset, int hd) {
//base case
if (root == NULL) return;
if (uset.find(hd) == uset.end()) {
uset.insert(hd);
cout<< root->val << ' ';
}
preorder(root->left, tmap, hd-1);
preorder(root->right, tmap, hd+1);
}
int TopView(TreeNode* root) {
vector<vector<int>> rst;
//sanity check
if (root == NULL) return rst;
unordered_set<int> uset;
//count the distance
preorder(root, uset, 0);
//get the vector
map<int,vector<int>> :: iterator it = tmap.begin();
return 0 ;
}
};
以上两个都是dfs version 的代码， 其实这个题目也可以用BFS来做，如果用BFS来做的话，
每遍历一层对已经遍历过的node的hd的值进行操作，
class TreeItem {
TreeNode* node;
int hd;
TreeItem(TreeNode* t1, int hd1) {
node = t1;
hd = hd1;
}
};
void TopView(TreeNode* root) {
//sanity cehck
if (root == NULL) return;
//BFS
queue<TreeItem*> explore;
unordered_set<int> uset;
explore.push(new TreeItem(root, 0));
while (!explore.empty()) {
TreeItem* tmp = explore.front();
explore.pop();
if (uset.find(tmp->hd) == uset.end()) {
uset.insert(hd);
cout << (tmp->node)->val;
}
if (tmp->node->left) explore.push(new TreeItem(tmp->node->left, tmp->hd-1));
if (tmp->node->right) explore.push(new TreeItem(tmp->node->right, tmp->hd+1));
}
return;
}
time complexity: O（n） for the unordered_set is hash set, O(1) to find a value;
如果这个题目对于BFS的解法不定义TreeItem这个object，那么必须要使用map来存储每个node的hd，因为
在遍历到下一层的时候不知道上一层的parent的hd是多少，这样对于map来说，insert的时间复杂度是O(logn)
时间复杂度为O（nlogn). 没有上面O（n)的情况好。
对于unordered_map: implementation 是hash_table, average insert , delete, find O(1), worset
case is O(N).
No comments:
Post a Comment