手帐 Blog

主题

复盘 · LC 199 二叉树的右视图 ​

题目 ​

题意 ​

从右侧看二叉树，从上到下，每一层能看到的那个节点值组成数组。

  • 空树 → []。
  • 等价于：每一层最右边的节点。

涉及算法 ​

标签一句话
BFS 层序每层取最后一个（接 102 的 size 模板）
DFS先右后左，每层第一次到达就记录；或同层后写覆盖

教程对照：18 · BFS 层序与 BST、16 · 二叉树遍历。昨日复盘：102 层序。

评价我的解法 ​

用「左 → 写当前 → 右」递归，按 depth 下标覆盖：resArr[depth] = root.val，同层后访问的节点盖住先访问的，最终留下偏右的值。

我的代码（摘自 199-二叉树的右视图/index.js，不含本地测例）：

javascript
var rightSideView = function (root) {
  const resArr = [];
  function preOrder(root, depth) {
    if (!root) {
      return;
    }
    const newDepth = depth + 1;
    preOrder(root.left, newDepth);
    resArr[depth] = root.val;
    preOrder(root.right, newDepth);
  }
  preOrder(root, 0);
  return resArr;
};

评价：

  1. 结果正确：同一深度后写覆盖前写；整棵树「左子树先于右子树」处理完，同层从左到右赋值，最后留下最右。本地用例与 AC 都对得上。
  2. 命名不准：函数叫 preOrder，实际赋值夹在左右之间，更接近中序访问顺序；面试口述别说成前序。
  3. 非最常见模板：面试更常讲 BFS「每层最后一个」，或 DFS「先右后左 + if (depth === res.length) push」。你这版能过，但要多一句解释「为何覆盖后是右视图」。
  4. 复杂度：时间 O(n)，空间 O(h) 递归栈 + O(h) 答案。

小结：右视图直觉有了；建议再默写一版 102 的 size 层序，每层取末元素，和昨天缺口对齐。

最佳题解 ​

BFS 层序取每层最后一个：

javascript
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const node = q.shift();
      if (i === size - 1) res.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
  }
  return res;
};

DFS 先右后左（只记每层第一次）：

javascript
var rightSideView = function (root) {
  const res = [];
  function dfs(node, depth) {
    if (!node) return;
    if (depth === res.length) res.push(node.val);
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }
  dfs(root, 0);
  return res;
};
  • 时间 O(n)，空间 O(n) / O(h)。
  • 为何更优（面试）：语义直接是「每层最右」，少依赖「覆盖顺序」这种隐含约定。

关联题目 ​

题为何相关
102. 二叉树的层序遍历右视图 = 层序每层最后一个
513. 找树左下角的值对称：偏左 / 最底层
116. 填充每个节点的下一个右侧节点指针层序横向连线

一句话带走 ​

右视图：层序每层取最后一个；DFS 就记「先右后左，每层只记第一次」。