Frontend Interview

Appearance

199. 二叉树的右视图 ​

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/

代码 ​

ts
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function rightSideView(root: TreeNode | null): number[] {
    if (root === null) {
        return [];
    }
    const res: number[] = [];
    const queue: TreeNode[] = [root];
    while (queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (i === size - 1) { // 最后一个
                res.push(node.val);
            }
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return res;
};

思路 ​

使用层序遍历（BFS），每层只记录最右边的节点：

  1. 使用队列进行层序遍历
  2. 对于每一层，记录当前层的节点数量 size
  3. 遍历当前层的所有节点：
    • 当遍历到该层最后一个节点时（i === size - 1），将其值加入结果数组
    • 将左右子节点依次加入队列
  4. 重复直到队列为空

关键点 ​

  • 层序遍历的核心是记录每层的节点数量，确保按层处理

  • 每层的最后一个节点就是从右侧看到的节点

  • 使用 queue.shift() 从队列头部取出节点，queue.push() 从尾部添加节点

  • 时间复杂度 O(n)，其中 n 是节点数量，需要遍历所有节点

  • 空间复杂度 O(n)，队列中最多存储一层的节点，最坏情况下为 n/2 个节点