199. 二叉树的右视图

🔥思路一：BFS（层序遍历）

核心逻辑

本解法采用 BFS（层序遍历） 的策略：

使用队列 Queue 进行标准的层序遍历。
每一层遍历时，记录当前层的节点数量 size。
遍历当前层的每个节点，只将当前层的最后一个节点（即 i == size - 1）的值加入结果列表。
这样就能得到每层最右侧的节点，即二叉树的右视图。

✅代码实现


class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                // 只将每一层的最后一个节点加入结果
                if (i == size - 1) {
                    list.add(t.val);
                }
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
        }
        return list;
    }
}

复杂度分析🚀
- 时间复杂度：O(N)，其中 N 是二叉树节点的总数。每个节点恰好入队和出队一次。
- 空间复杂度：O(N)，队列在最坏情况下（完全二叉树最后一层）存储 N/2 个节点。

🔥思路二：DFS（深度优先搜索）

核心逻辑

本解法采用 DFS（深度优先搜索） 的策略,代码更简洁优雅：

利用递归进行深度优先遍历，优先访问右子树，再访问左子树（原因如下：题目要求是右视图映射根右左s最优选择）
使用一个变量 depth 记录当前递归深度
当 depth == list.size() 时，说明这是该深度第一次被访问到的节点（由于优先遍历右子树，第一次访问的一定是该层最右侧的节点），将其加入结果列表。
这样可以保证每个深度只添加一个节点，且正是右视图所需的节点。

✅代码实现

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return helper(root, list, 0);
    }
    
    private List<Integer> helper(TreeNode root, List<Integer> list, int depth) {
        if (root == null) {
            return list;
        }
        // 当前深度首次遇到节点，加入结果
        if (depth == list.size()) {
            list.add(root.val);
        }
        // 优先遍历右子树
        helper(root.right, list, depth + 1);
        helper(root.left, list, depth + 1);
        return list;
    }
}

复杂度分析🚀
- 时间复杂度：O(N)，其中 N 是二叉树节点总数。每个节点恰好被访问一次。
- 空间复杂度：O(N)，主要消耗在递归调用的栈空间上，最坏情况下（树呈链状）深度为 N。

总结一下自己遇到d一些问题⚠️ ⚠️ ⚠️ ：

1.BFS倒是没什么，思路挺清晰，就是层序遍历，内循环到最后一个元素时则为第一视图元素

2.关键是DFS，写的时候没有用deepth作为判断条件，导致和后序遍历一样，加入了所有元素，这让我对deepth存在的意义产生了一些困惑，当deepth为0时代表第一层，size为0时说明list里没有元素，它应该先存第一层d元素，递归深入也同理，二者某种程度上形成映射关系（相等时要存d就是当前ro'od值），那么此时list就只有右视图元素->(（当你右树加完回来调用左树，二者不相等自然不会添加元素，那么也就保证了元素仅包含右视图元素）