题目描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
相关话题： 树、深度优先搜索、广度优先遍历 难度： 中等

解法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;
    }
}