LeetCode - 199. 二叉树的右视图

题目

199. 二叉树的右视图 - 力扣（LeetCode）

思路

右视图是指从树的右侧看，对于每一层，只能看到该层最右边的节点。实现思路是：

• 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树
• 记录每个节点的深度
• 对于每一层，只保留第一个访问到的节点（因为先访问右侧，所以这个节点就是该层最右边的节点）

图解

    1
   / \
  2   3
 / \   \
4   5   6

DFS访问顺序（先右后左）是：1 -> 3 -> 6 -> 2 -> 5 -> 4

• 访问节点1（深度0）：result=[]，depth=0，满足depth==result.size()，将1加入result=[1]

• 访问节点3（深度1）：result=[1]，depth=1，满足depth==result.size()，将3加入result=[1,3]

• 访问节点6（深度2）：result=[1,3]，depth=2，满足depth==result.size()，将6加入result=[1,3,6]

• 访问节点2（深度1）：result=[1,3,6]，depth=1，不满足depth==result.size()，不操作

• 访问节点5（深度2）：result=[1,3,6]，depth=2，不满足depth==result.size()，不操作

• 访问节点4（深度2）：result=[1,3,6]，depth=2，不满足depth==result.size()，不操作

最终result=[1,3,6]，正好是树的右视图。

详细过程

初始化：

• 创建一个结果数组result来存储右视图的节点值
• 从根节点开始，深度为0

DFS遍历：

• 如果当前节点为空，直接返回
• 检查当前深度是否等于结果数组的长度
• 如果是，说明这是当前深度第一个被访问的节点，将其值加入结果数组
• 如果不是，说明该深度已经有节点被加入结果，不做操作
• 先递归访问右子树（深度+1），再递归访问左子树（深度+1）

先右后左的重要性：

• 由于我们先访问右子树再访问左子树，对于每一层，最右边的节点会被最先访问
• 结合"深度等于结果数组长度"的条件，确保只有每层最右边的节点被加入结果

读者的错误写法

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        dfs(root,0,result);
    }

    void dfs(TreeNode* root,int depth, vector<int> result)
    {
        if(!root)
        {
            return;
        }

        if(depth == result.size())
        {
            dfs(root->right,depth,result);
            dfs(root->left,depth,result);
        }
    }
}; 

参数传递问题：

• dfs 函数中的 vector<int> result 应该是引用类型 vector<int>& result，否则你对 result 的修改不会反映到 rightSideView 函数的 result 变量上

缺少添加节点值的语句：

• 当 depth == result.size() 时，应该将当前节点值添加到 result 中，但代码中缺少这一步

递归调用错误：

• 在 if(depth == result.size()) 内部调用 DFS 是不对的，应该在判断外部递增深度后调用

• 递归调用时没有递增 depth

正确的写法

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        dfs(root,0,result);
        return result;
    }

    void dfs(TreeNode* root,int depth, vector<int>& result)
    {
        if(!root)
        {
            return;
        }

        if(depth == result.size())
        {
            result.push_back(root->val);
        }
        dfs(root->right,depth+1,result);
        dfs(root->left,depth+1,result);
    }
};