题目
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4]
1 <— / 2 3 <— \ 5 4 <—
思路
dfs，按照根、右、左的顺序遍历，可以保证每层第一个访问的是最右边的节点。用深度做比较，结果集中存放的元素个数，和深度是对应的。当遍历到新的一层时，如果depth==结果集大小，说明本层元素还未放入，就将当前元素放入。
代码
List
<Integer> res
= new ArrayList<>();
public List
<Integer> rightSideView(TreeNode root
) {
dfs(root
,0);
return res
;
}
public void dfs(TreeNode root
,int depth
){
if(root
==null
) return;
if(depth
==res
.size()){
res
.add(root
.val
);
}
dfs(root
.right
,depth
+1);
dfs(root
.left
,depth
+1);
}
思路
BFS，每层遍历的最后一个元素放入结果集中。
代码
public List
<Integer> rightSideView2(TreeNode root
){
List
<Integer> res1
= new ArrayList<>();
if (root
== null
) {
return res1
;
}
Queue
<TreeNode> queue
= new LinkedList<>();
queue
.add(root
);
while(!queue
.isEmpty()){
int size
= queue
.size();
for(int i
= 0;i
<size
;i
++){
TreeNode head
= queue
.poll();
if(head
.left
!=null
){
queue
.add(head
.left
);
}
if(head
.right
!=null
){
queue
.add(head
.right
);
}
if(i
==size
-1) res1
.add(head
.val
);
}
}
return res1
;
}
