题目描述
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
相关话题： 树、深度优先搜索、广度优先遍历 难度： 中等
-
解法1：层次遍历
第一眼是我熟悉的层次遍历可以做，定义一个变量end记录当前层的最后一个节点，在该层的遍历过程中不断更新下一层的最后一个节点nextEnd。
遍历到该层的最后一个节点后更新end，end = nextEnd。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
if(root == null) return new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<Integer> res = new ArrayList<Integer>();
TreeNode end = root;
TreeNode nextEnd = null;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode x = queue.poll();
if(x.left != null){
nextEnd = x.left;
queue.offer(x.left);
}
if(x.right != null){
nextEnd = x.right;
queue.offer(x.right);
}
if(end == x){
res.add(x.val);
end = nextEnd;
}
}
return res;
}
}
- 解法2：递归
