跳到主要内容

二叉树的右视图

问题​

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

示例：

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

    1        ←  你从右边看
   / \
  2   3      ←
   \   \
    5   4    ←

输出：[1, 3, 4]

来源：LeetCode 199. 二叉树的右视图

答案​

方法一：BFS 层序遍历（推荐）​

核心思路：每一层的最后一个节点就是右视图能看到的节点。

rightSideView.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];

  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;

      // 每层的最后一个节点
      if (i === levelSize - 1) result.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return result;
}
复杂度分析
  • 时间复杂度：O(n)O(n) — 每个节点访问一次
  • 空间复杂度：O(n)O(n) — 队列最多存一层节点

方法二：DFS 先遍历右子树​

核心思路：先走右子树再走左子树的 DFS。每层第一个访问的节点就是右视图中的。

rightSideViewDFS.ts
function rightSideView(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null, depth: number): void {
    if (!node) return;

    // 如果当前深度首次到达，这个节点就是右视图中的
    if (depth === result.length) result.push(node.val);

    // 先右后左
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }

  dfs(root, 0);
  return result;
}

关键理解：

  • depth === result.length 意味着这一层还没有节点加入结果
  • 先遍历右子树，所以右边的节点一定先被加入
  • 如果右边没有节点，左边的节点也能被看到

常见面试追问​

Q1: 如何获取左视图？​

答案：BFS 取每层第一个节点，或 DFS 先遍历左子树：

function leftSideView(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null, depth: number): void {
    if (!node) return;
    if (depth === result.length) result.push(node.val);
    dfs(node.left, depth + 1);  // 先左后右
    dfs(node.right, depth + 1);
  }

  dfs(root, 0);
  return result;
}

Q2: BFS 中 shift() 性能问题？​

答案：Array.shift() 是 O(n)O(n) 操作。优化方式：

  1. 用指针代替 shift
  2. 用双端队列（Deque）
  3. 在面试中一般指出即可，实际影响不大
// 用指针优化，避免 shift
let front = 0;
while (front < queue.length) {
  const levelSize = queue.length - front;
  for (let i = 0; i < levelSize; i++) {
    const node = queue[front++]; // 用指针前进
    // ...
  }
}

Q3: 这道题和层序遍历的关系？​

答案：右视图是层序遍历的子集 — 只取每层最后一个元素。掌握 层序遍历 后，很多变体都能秒杀：

变体取法
右视图每层最后一个
左视图每层第一个
锯齿形遍历奇数层和偶数层方向交替
每层最大值每层取 max
每层平均值每层求平均

相关链接​