199 二叉树的右视图

一、题目

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

二、题解

方法一：BFS 层序遍历

思路：使用 BFS 层序遍历。

1. 核心思路

题目要求返回从右侧看到的节点，也就是每一层最右边的节点。

因此可以使用层序遍历，一层一层地遍历二叉树。

核心思想是：

  • 每次遍历一整层节点；
  • 对于当前这一层，最后遍历到的节点就是最右边的节点；
  • 把每一层的最后一个节点加入结果数组。

2. 具体步骤

  1. 如果 root == null，说明是空树，直接返回空列表。
  2. 创建队列 queue，将根节点加入队列。
  3. 当队列不为空时，先记录当前层的节点数量 size。
  4. 遍历当前层的所有节点。
  5. 如果当前节点是这一层的最后一个节点，就加入结果数组。
  6. 将当前节点的左孩子和右孩子加入队列。
  7. 最后返回结果数组。

3. 关键逻辑

if (i == size - 1) {
    result.add(node.val);
}

解释：

  • size 表示当前这一层的节点数量；
  • i == size - 1 说明当前节点是这一层的最后一个节点；
  • 因为层序遍历是从左到右遍历，所以最后一个节点就是这一层最右边的节点；
  • 因此需要把它加入结果数组。

4. 代码

/**
 * 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 {
    public List<Integer> rightSideView(TreeNode root) {
        // 1. 定义结果数组
        List<Integer> result = new ArrayList<>();

        // 2. 处理特殊情况
        if (root == null) {
            return result;
        }

        // 3. 定义队列，用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 4. 开始层序遍历
        while (!queue.isEmpty()) {
            // 当前层的节点数量
            int size = queue.size();

            // 遍历当前这一层
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // 如果是当前层最后一个节点，就加入结果
                if (i == size - 1) {
                    result.add(node.val);
                }

                // 左孩子不为空，加入队列
                if (node.left != null) {
                    queue.offer(node.left);
                }

                // 右孩子不为空，加入队列
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        // 5. 返回结果
        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点都会被遍历一次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：队列中最多可能存放一层的节点，最坏情况下需要 O(n)O(n) 的空间。

方法二：DFS 右优先遍历

思路：使用 DFS 深度优先遍历。

1. 核心思路

从右侧看二叉树时，每一层最先看到的应该是最右边的节点。

因此可以使用 DFS，并且按照下面的顺序遍历：

根节点 -> 右子树 -> 左子树

这样可以保证每一层第一次访问到的节点，就是这一层最右边的节点。

这种方法的核心是：

  • 先访问当前节点；
  • 再优先访问右子树；
  • 如果当前深度第一次被访问到，就把当前节点加入结果数组。

2. 具体步骤

  1. 定义结果数组 result。
  2. 从根节点开始进行 DFS，初始深度为 0。
  3. 如果当前节点为空，直接返回。
  4. 如果 depth == result.size()，说明当前深度第一次被访问到。
  5. 因为 DFS 是先遍历右子树，所以当前节点就是这一层最右边的节点。
  6. 先递归遍历右子树，再递归遍历左子树。
  7. 最后返回结果数组。

3. 关键逻辑

if (depth == result.size()) {
    result.add(root.val);
}

解释：

  • depth 表示当前节点所在的层数；
  • result.size() 表示目前已经记录了多少层的右视图节点；
  • 如果 depth == result.size()，说明这一层还没有记录过节点；
  • 因为我们先遍历右子树，所以第一次访问到的一定是这一层最右边的节点。

4. 代码

/**
 * 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 {
    // 定义结果数组
    private List<Integer> result = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        // 从根节点开始 DFS，根节点深度为 0
        dfs(root, 0);

        return result;
    }

    private void dfs(TreeNode root, int depth) {
        // 1. 递归终止条件
        if (root == null) {
            return;
        }

        // 2. 如果当前深度第一次被访问到
        // 说明当前节点就是这一层最右边的节点
        if (depth == result.size()) {
            result.add(root.val);
        }

        // 3. 先遍历右子树
        dfs(root.right, depth + 1);

        // 4. 再遍历左子树
        dfs(root.left, depth + 1);
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点都会被访问一次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(h)O(h)

说明：递归调用栈的深度取决于二叉树高度，h 表示树的高度。

最坏情况下，二叉树退化成链表，空间复杂度是 O(n)O(n)。

如果二叉树比较平衡，空间复杂度是 O(log⁡n)O(\log n)。

评论