0199.二叉树的右视图
难度：🟡 中等
标签：树、深度优先搜索、广度优先搜索、二叉树
链接：199. 二叉树的右视图
题目描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
解题思路
核心思想
本题的核心是找到二叉树每一层的最右边的那个节点。这个问题可以通过两种主要的遍历方式来解决：广度优先搜索（BFS）和深度优先搜索（DFS）。
思路选择
广度优先搜索 (BFS)：这是最直观的思路。我们对二叉树进行层序遍历，对于每一层，最后一个被访问到的节点就是该层的最右侧节点。我们只需将每一层的最后一个节点的值记录下来即可。
深度优先搜索 (DFS)：我们也可以通过 DFS 解决。关键在于利用递归的顺序。如果我们按照 “根节点 -> 右子树 -> 左子树” 的顺序进行遍历，那么对于每一个深度（层级），我们访问到的第一个节点就一定是该层最右边的节点。我们只需记录每个深度第一次访问到的节点值即可。
关键步骤 (BFS)
处理边界情况：如果树为空，返回空数组。
初始化：创建一个队列
queue并将根节点root入队。创建一个结果数组result。层序遍历：当
queue不为空时，持续循环。 a. 在循环开始时，记录当前queue的长度levelSize。 b. 启动一个内层循环，执行levelSize次。 c. 在内层循环中，从队列中取出一个节点。 d. 将该节点的左、右子节点（如果不为空）依次入队。 e. 记录最右节点：当内层循环进行到最后一次时（i === levelSize - 1），当前节点就是该层的最右侧节点，将其值推入result数组。返回结果：遍历结束后，返回
result。
代码实现 (推荐 - BFS)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function (root) {
if (!root) return [];
const queue = [root];
const result = [];
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;
};
原始代码分析 (用户提供)
您提供的代码采用了一种非常巧妙的深度优先搜索（DFS）来解决问题，逻辑正确且高效。
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function (root) {
if (root === null) return [];
// 使用 stack 进行 DFS, node 包含了层级信息
let stack = [{ level: 0, node: root }];
let result = [];
while (stack.length !== 0) {
// pop() 使其成为深度优先
const { level, node } = stack.pop();
// 如果该层级第一次被访问，则记录节点值
if (result[level] === undefined) {
result[level] = node.val;
}
// 先推入左子节点，再推入右子节点
// 这保证了 pop 时，会优先处理右子树的节点
if (node.left) stack.push({ level: level + 1, node: node.left });
if (node.right) stack.push({ level: level + 1, node: node.right });
}
return result;
};
优点：此实现堪称 DFS 解法的典范。通过 “根 -> 右 -> 左” 的遍历顺序（由
push左再push右，然后pop实现），保证了每一层最先被访问到并记录下来的节点，一定是该层最右边的节点。代码风格: 代码非常清晰，逻辑严谨，是一个优秀的实现。
复杂度分析
时间复杂度：O(n) 其中 n 是树的节点总数。每个节点都会被访问一次。
空间复杂度：
BFS: O(w)，其中 w 是树的最大宽度。
DFS: O(h)，其中 h 是树的高度。
相关题目
总结
本题是考察二叉树遍历的经典题目。BFS 的解法更符合“按层”观察的题意，直观易懂。而 DFS 的解法通过巧妙地设计遍历顺序，也能高效地解决问题，展示了 DFS 灵活的应用。两种方法都应该掌握。