2018年4月16日 下午3:54
Binary Tree Right Side View - LeetCode
- 遍历的对象是一个边建立边遍历的队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class Solution {
public:
std::vector<int> rightSideView(TreeNode* root) {
std::queue<std::pair<TreeNode*, int>> Q;
std::vector<int> vec;
//int代表这层数
std::pair<TreeNode*, int> temp_pair;
temp_pair.first = root;
temp_pair.second = 0;
Q.push(temp_pair);
generate(Q, vec);
return vec;
}
private:
//这回同样是遍历，但是遍历的对象不是树，而是队列
//对于队列来说，我们即放入也拿出
void generate(std::queue<std::pair<TreeNode*, int>> &Q, std::vector<int> &vec){
if(Q.empty()){
return;
}
//当前
std::pair<TreeNode*, int> current = Q.front();
Q.pop();
if(Q.empty() || current.second != Q.front().second){
vec.push_back((current.first)->val);
}
//给队列添加
std::pair<TreeNode*, int> temp_pair;
if((current.first)->left){
temp_pair.first = (current.first)->left;
temp_pair.second = current.second+1;
Q.push(temp_pair);
}
if((current.first)->right){
temp_pair.first = (current.first)->right;
temp_pair.second = (current.second+1);
Q.push(temp_pair);
}
//遍历下一个
generate(Q, vec);
}
};