【Hot 100 刷题计划】 LeetCode 199. 二叉树的右视图 | C++ DFS 逆序遍历

LeetCode 199. 二叉树的右视图 题目描述题目级别中等给定一个二叉树的根节点root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例 1:输入root [1,2,3,null,5,null,4]输出[1,3,4] 破题思路根-右-左 DFS 探测这道题最巧妙的解法不是层序遍历而是带深度的深度优先搜索 (DFS)。核心逻辑我们按照“根节点 - 右子树 - 左子树”的顺序进行递归。为什么要先递归右子树因为这样可以保证在每一个深度层级我们访问到的第一个节点一定是该层最右边的节点。我们维护一个结果数组res。在递归过程中如果当前res的长度正好等于当前的深度level就说明当前深度是第一次被访问那么当前节点就是我们要找的“右侧视图节点”。性能优势相比于 BFS 需要维护一个队列这种 DFS 写法空间复杂度更低且代码极其简洁。 C 代码实现 (DFS 规范版)classSolution{public:vectorintrightSideView(TreeNode*root){vectorintres;dfs(root,0,res);returnres;}// 重点通过引用传递 res并在递归时先走右边voiddfs(TreeNode*root,intdepth,vectorintres){if(!root)return;// 如果结果集的大小等于当前深度说明这一层最右边的节点刚被发现if(res.size()depth){res.push_back(root-val);}// 先往右边冲保证右边节点先占坑dfs(root-right,depth1,res);// 再往左边走dfs(root-left,depth1,res);}};