day145—递归—二叉树的右视图（LeetCode-199）
题目描述
给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
解决方案：
这段代码的核心功能是获取二叉树的右视图（即从二叉树右侧观察能看到的节点值，按从上到下的顺序输出），采用「递归 + 前序遍历（优先访问右子树）」的思路，通过深度标记记录每一层的第一个（最右侧）节点，时间复杂度O(n)（n为节点数），空间复杂度O(h)（h为树的高度），是该问题的经典递归解法。
核心逻辑
代码的核心思路是 “优先遍历右子树，每一层只记录第一个访问到的节点（即最右侧节点）”，通过深度和结果数组的长度关联来实现：
- 全局结果数组初始化：定义
ans数组保存右视图节点值，初始为空； - 递归辅助函数
f：参数为当前节点node和当前深度depth：- 边界条件：若当前节点为空，直接返回；
- 深度更新：当前节点非空时，深度
+1（表示当前节点所在层）； - 记录最右侧节点：若
ans数组的长度小于当前深度（说明该层还未记录任何节点），将当前节点值加入ans（因优先遍历右子树，这是该层第一个被访问的节点，即最右侧节点）； - 优先递归右子树：先遍历当前节点的右子树，再遍历左子树（保证每一层先访问右节点）；
- 主函数触发遍历：调用
f(root, 0)（初始深度为 0，未访问任何节点），最终返回ans即为右视图结果。
总结
- 核心思路：利用 “优先遍历右子树 + 深度标记”，让每一层的第一个节点就是最右侧节点，仅记录该节点即可；
- 关键细节：
ans.size() < depth是判断 “是否为该层第一个节点” 的核心条件，确保每一层只记录一个节点； - 效率特点：每个节点仅遍历一次，时间
O(n)；递归栈空间取决于树的高度，平衡树为O(log n)，退化为链表时为O(n)。
函数源码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> ans={}; void f(TreeNode* node,int depth){ if(!node) return; depth+=1; if(ans.size()<depth){ ans.push_back(node->val); } f(node->right,depth); f(node->left,depth); } vector<int> rightSideView(TreeNode* root) { f(root,0); return ans; } };