Leetcode 199. 二叉树的右视图

力扣传送门

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

示例 1:

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

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

解题思路：

我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。

这样一来，我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。

上图表示了问题的一个实例。红色结点自上而下组成答案，边缘以访问顺序标号。

代码实现：

dfs:

这段代码实现了二叉树的右视图，但是使用了深度优先搜索（DFS）的思想来遍历二叉树。

1. 首先，创建一个空的列表 res，用于存储右视图的节点值。
2. 检查根节点 root 是否为空，如果为空，则直接返回空列表 res。
3. 调用递归函数 dfs(root, 0) 来进行深度优先搜索。
4. 在递归函数 dfs 中，传入当前节点 root 和当前层级 level。
5. 如果当前节点 root 为空，直接返回。
6. level == res.size() 的条件判断意味着当前层级 level 等于结果列表 res 的大小。在 dfs 函数中，我们使用 res 列表来记录每一层级的最右侧节点的值。因此，res 列表的大小就代表了当前已经遍历到的层级数。当 level 等于 res 列表的大小时，说明我们还没有遍历到当前层级的最右侧节点，因此将当前节点的值 root.val 添加到 res 列表中。这样可以确保每一层级只选择最右侧的节点值作为右视图的结果。如果 level 小于 res 列表的大小，表示当前层级已经有节点值被添加到 res 列表中，所以无需再添加当前节点的值。通过这个条件判断，我们可以保证 res 列表中存储的是每一层级的最右侧节点值，从而得到二叉树的右视图。
7. 以右子节点为根节点，递归调用 dfs(root.right, level + 1)，遍历右子树。
8. 以左子节点为根节点，递归调用 dfs(root.left, level + 1)，遍历左子树。
9. 这样，通过先遍历右子树再遍历左子树的方式，确保每层级只取最右侧的节点值，从而得到二叉树的右视图。
10. 当递归结束时，所有节点都已经遍历完毕，res 列表中存储的就是二叉树的右视图节点值的集合。
11. 返回列表 res 作为函数的结果。

/**
 * 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 {
    List<Integer> res = new ArrayList();
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return res;
        }
        dfs(root,0);
        return res;
    }

    public void dfs(TreeNode root,int level){
        if(root == null){
            return;
        }
        if(level == res.size()){
            res.add(root.val);
        }

        dfs(root.right,level+1);
        dfs(root.left,level+1);
    }
}

bfs:

该算法使用了广度优先搜索（BFS）的思想来遍历二叉树。具体解题思路如下：

1. 首先，创建一个空的列表 ans，用于存储右视图的节点值。
2. 检查根节点 root 是否为空，如果为空，则直接返回空列表 ans。
3. 创建一个队列 q，并将根节点 root 入队。
4. 进入循环，只要队列 q 不为空，就执行以下操作：
   1. 初始化变量 count，用于记录当前层级的节点数量。
   2. 遍历当前层级的节点，从 0 到 count-1，执行以下操作：
      1. 出队一个节点 node。
      2. 如果 node 的左子节点不为空，将其加入队列 q。
      3. 如果 node 的右子节点不为空，将其加入队列 q。
      4. 如果当前节点是当前层级的最后一个节点（即 i == count - 1），将其值 node.val 添加到 ans 列表中。
   3. 完成当前层级的遍历后，继续下一层级的遍历。
5. 当循环结束时，所有层级的节点都已经遍历完毕，ans 列表中存储的就是二叉树的右视图节点值的集合。
6. 返回列表 ans 作为函数的结果。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int count;
        while (!q.isEmpty()) {
            count = q.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
                if (i == count - 1) ans.add(node.val);
            }
        }
        return ans;
    }
}