199. 二叉树的右视图

---

题目

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

示例： 示例 1:

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

示例 2:

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

---

解题思路

核心方法

1. 递归法（深度优先搜索 DFS）：优先遍历右子树，当当前深度等于结果列表的大小时，说明该节点是当前层的最右节点，将其加入结果列表。
2. 迭代法（广度优先搜索 BFS）：层序遍历二叉树，记录每一层的最后一个节点，即为右视图可见的节点。

算法步骤（递归法）

1. 初始化结果列表：创建一个列表存储右视图的节点值。
2. 递归遍历：
   • 若当前节点为 null，直接返回。
   • 若当前深度等于结果列表的大小，说明该节点是当前层的最右节点，将其值加入结果列表。
   • 先递归遍历右子树，再递归遍历左子树，确保右子树节点优先被访问。
3. 返回结果：遍历完成后，返回结果列表。

---

代码实现

递归法（Java）

import java.util.*;

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> ans = new ArrayList<>();
    
    public List<Integer> rightSideView(TreeNode root) {
        rightSideView(root, 0);
        return ans;
    }
    
    public void rightSideView(TreeNode root, int depth) {
        if (root == null) return;
        if (ans.size() == depth) ans.add(root.val);
        rightSideView(root.right, depth + 1);
        rightSideView(root.left, depth + 1);
    }
}

迭代法（Java）

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                // 记录当前层的最后一个节点
                if (i == size - 1) ans.add(curr.val);
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
        }
        return ans;
    }
}

---

复杂度分析

递归法

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

迭代法

• 时间复杂度：O(n)，每个节点会被入队和出队一次。
• 空间复杂度：O(m)，m 是二叉树的最大宽度，最坏情况下（完全二叉树）为 O(n)。

---

总结

1. 递归法通过优先访问右子树，确保每一层的第一个被访问的节点是最右节点，实现简洁高效。
2. 迭代法通过层序遍历记录每一层的最后一个节点，逻辑直观，避免了递归栈溢出的风险。
3. 两种方法的时间效率一致，空间效率取决于树的形态，递归法受高度影响，迭代法受宽度影响。

---