算法 - 二叉树的右视图

Posted on

1. 题目

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

示例:

1
2
3
4
5
6
7
8
输入: [1,2,3,null,5,null,4]
        1            <---
      /   \
     2     3         <---
      \     \
       5     4       <---
输出: [1,3,4]
解释: 每一层最右边的节点构成右视图。

2. 解题思路

「右视图」本质是求每一层的最右一个节点。两种主流做法：

2.1 BFS 层序遍历（最直观）

用队列逐层遍历，记录每层的节点个数 levelSize，取该层最后一个出队的节点值加入结果。

  • 时间复杂度：O(n)，空间复杂度：O(n)（队列最宽一层的节点数）。

2.2 DFS（根 → 右 → 左）

关键是先遍历右子树。对每一层，第一个被访问到的节点就是右视图节点。用 depth 记录层数，当 res.length === depth 时说明这一层还没收集过节点，push 当前值。

  • 因为先走右，所以「第一个到达」的必然是该层最右侧节点。

3. TypeScript 实现

树节点定义：

1
2
3
4
5
6
7
8
9
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0) {
        this.val = val;
        this.left = this.right = null;
    }
}

3.1 BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function rightSideView(root: TreeNode | null): number[] {
    if (!root) 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;
}

3.2 DFS（先右后左）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function rightSideViewDFS(root: TreeNode | null): number[] {
    const res: number[] = [];

    const dfs = (node: TreeNode | null, depth: number) => {
        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;
}

4. 面试延伸

  • 左视图：BFS 取每层 i === 0；DFS 改成「先左后右」。
  • 俯视图 / 剖面等变形考察的是对遍历顺序与层/列归属的理解。
  • 追问：DSF 解法空间上省去队列，但递归栈最坏 O(h)，h 为树高； skewed tree 下退化为 O(n)。
  • queue.shift() 在 JS 中是 O(n)，严格优化可用双指针索引或自定义队列，面试点出即可。

难度：中等 | LeetCode 199 | BFS/DFS 层序思想