LeetCode 199. 二叉树的右视图题解

news/2025/2/10 8:04:34/

题目描述

给定一棵二叉树的根节点，想象你站在它的右侧，返回你能看到的节点值（从上到下的顺序）。

示例：

输入：1/ \2   3\   \5   4
输出：[1,3,4]
解释：站在右侧时，只能看到每层最右边的节点

解题思路

这道题的核心是找到每一层最右边的节点。我们可以用递归的 DFS（深度优先搜索）来解决，但需要一点小技巧：

右子树优先：遍历时先访问右子树，再访问左子树。这样当第一次到达某一深度时，遇到的节点一定是该层最右侧的节点。
深度标记：维护一个全局变量 max_depth 记录当前已访问过的最大深度。只有当当前深度超过 max_depth 时，才记录节点值并更新最大深度。

举个栗子🌰：

对于示例中的树，遍历顺序是 1 → 3 → 4 → 2 → 5
当访问到节点 3（深度2）时，发现深度超过之前的 max_depth（初始为0），记录 3
接着访问 4（深度3），记录 4
最后访问 5（深度3），此时 max_depth 已经是3了，不再记录

代码实现

class Solution {
public:int max_depth = 0;  // 全局变量，记录当前最大深度void traversal(TreeNode *root, int depth, vector<int> &res) {if (!root) return;depth++;  // 进入节点时深度+1// 关键判断：首次到达新深度时记录节点值if (depth > max_depth) {max_depth = depth;     // 更新最大深度res.push_back(root->val); // 记录右侧节点}// 先递归右子树，再递归左子树（右子树优先）traversal(root->right, depth, res);traversal(root->left, depth, res);}vector<int> rightSideView(TreeNode* root) {if (!root) return {};  // 处理空树vector<int> res;traversal(root, 0, res);  // 初始深度为0return res;}
};