05 August 2008
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
1
2
3
4
5
6
7
8
9
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
将二叉树的右视图作为数组打出来，依然是树的的两种遍历方式，BFS和DFS
1) BFS
进行层次遍历，记录下每层的最后一个元素。
时间复杂度： O(N)，每个节点都入队出队了 1 次。
空间复杂度： O(N)，这个是最典型的BFS，使用了额外的队列空间。
2) DFS
前序遍历稍微改变一下，按照「根结点 -> 右子树 -> 左子树」的顺序来遍历，因为要看右视图，所以确保每层都是最先访问最右边的节点的。
时间复杂度： O(N)，每个节点都访问了 1 次。
空间复杂度： O(N)，因为这不一定是一棵平衡二叉树，二叉树的深度最少是 logN, 最坏的情况下会退化成一条链表，深度就是 N，因此递归时使用的栈空间是 O(N) 的。
BFS
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int curSize = queue.size(); //当前层的节点数量
for (int i = 0; i < curSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == curSize - 1) {
result.add(node.val); // 将当前层的最右边的节点加入到结果集中
}
}
}
return result;
}
}
DFS
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
class Solution {
List<Integer> result;
public List<Integer> rightSideView(TreeNode root) {
result = new ArrayList<>();
dfs(root, 0); // 从根节点开始访问，根节点深度是0
return result;
}
private void dfs(TreeNode node, int depth) {
if (node == null) {
return;
}
// 如果当前节点所在深度还没有出现在result里，也就是"每一层"的第一个节点还没有开始计数，
// 说明在该深度下当前节点是第一个被访问的节点(也就是最右节点)，因此将当前节点加入result中。
// 注意深搜的遍历顺序，一条道走到底
if (depth == result.size()) {
result.add(node.val);
}
depth++;
// 先访问 当前节点，再递归地访问 右子树 和 左子树。
dfs(node.right, depth);
dfs(node.left, depth);
}
}