剑指offer046-二叉树的右侧视图
题目
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
提示:
- 二叉树的节点个数的范围是
[0,100]
-100 <= Node.val <= 100
注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/
Related Topics
树深度优先搜索广度优先搜索二叉树思路
（1）一开始以为是右侧的节点，直接访问右侧节点了，写出如下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
findRight(root, res);
return res;
}
void findRight(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
res.add(node.val);
if (node.right != null) {
findRight(node.right, res);
}
}
}
|
这个是有问题的，因为右侧节点可能不存在，这样右侧是能看到左侧的节点的
（2）调整过来就层次遍历了
代码
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
| class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode t = queue.poll();
if(t.left != null){
queue.offer(t.left);
}
if(t.right != null){
queue.offer(t.right);
}
if(i == size - 1){
res.add(t.val);
}
}
}
return res;
}
}
|
1
2
3
| 解答成功:
执行耗时:1 ms,击败了87.56% 的Java用户
内存消耗:37.1 MB,击败了35.01% 的Java用户
|