2021/10/15 二叉树的右视图 叶龄徽

leetcode链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/

题目

题目描述：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: []

方法一：深度优先遍历

我们先对树进行深度优先搜索，我们总是先访问右子树。
那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。
然后我们存储每个深度访问的第一个节点，一旦我们知道了树的层数，就可以得到最终结果的数组。

算法：按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。

class Solution {
    List<Integer> res = new ArrayList<>();  //存放最终结果
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    }
    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
         // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，
        //因此将当前节点加入res中。
        if (depth == res.size()) {   
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

方法二：广度优先遍历

对二叉树进行层次遍历，所以对于每层来说，最右边的结点一定是最后被遍历到的。【二叉树的层次遍历可以用广度优先搜索实现】
执行广度优先搜索，左结点排在右结点之前，这样，我们对每一层都从左到右访问。因此，只保留每个深度最后访问的结点，我们就可以在遍历完整棵树后得到每个深度最右的结点。

算法：利用广度优先搜索进行层次遍历，记录下每层的最后一个元素。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {    
        List<Integer> res = new ArrayList<>();  //存放最终结果
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  //根节点入队
        while (!queue.isEmpty()) {
            int size = queue.size();  //当前队列大小，即当前层的节点个数
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}