【刷题日记】二叉树-二叉树的右视图-L199-Medium
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
思路
- 二叉树的层序遍历，但仅仅在结果集中加入每层的最后一个节点的值。
- 若考虑通过深度遍历去遍历右子树，但从 右视图 视角来看，如果右子树为空，则右视图会看到左子树的最右边的节点，因此这个思路不正确。
学习点
代码
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
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (root == nullptr)
return res;
queue<TreeNode*> qe;
qe.push(root);
while (!qe.empty())
{
int node_num = qe.size();
for (int i = 0; i < node_num; i++)
{
auto tmp = qe.front();
qe.pop();
if (i == node_num - 1)
res.push_back(tmp->val);
if (tmp->left)
qe.push(tmp->left);
if (tmp->right)
qe.push(tmp->right);
}
}
return res;
}
};
|
