leetcode199 二叉树的右视图

小问题：if(!q.empty()) 这个条件会导致只处理一层，而不会处理所有层。正确的做法应该是用 while(!q.empty()) 循环处理每一层。
 

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;
        if(root == nullptr){
            return res;
        }
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            int everylevel;
            
            for(int i = 0; i < size; i++){
                TreeNode* cur = q.front();
                q.pop();
                if(i == size-1){
                    everylevel = cur->val;
                }
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            res.push_back(everylevel);
        }
        return res;
    }
};

1. TreeNode* cur = q.front(); q.pop(); 放在 for 循环外

   • 这样会导致每次循环都处理同一个节点，而不是遍历当前层的所有节点。

2. everylevel 的赋值逻辑

   • 应该在 for 循环内更新 cur 节点，并在 i == size-1 时记录当前层的最后一个节点。

递归：

class Solution {
private:
    void recursion(TreeNode*cur, int level, vector<int>& res){
        if(cur == nullptr) return;

        if(level == res.size()) res.push_back(cur->val);
        if(cur->right) recursion(cur->right, level+1, res);
        if(cur->left) recursion(cur->left, level+1, res);
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        recursion(root, 0, res);
        return res;
    }
};

1. 调整递归顺序：

   • 先递归右子树，再递归左子树（recursion(cur->right, ...) 在前），确保右节点优先被处理。

2. 层数从 0 开始：

   • 初始调用 recursion(root, 0, res)，使 level 和 res.size() 对齐。

3. DFS 顺序：根 → 右 → 左（类似前序遍历的变种）。

4. 层数判断：

   • if (level == res.size())：说明当前节点是该层第一个被访问的（由于先右后左，它是最右节点）。

   • 将该节点的值加入 res。

1. res 的类型不同：

   • 你的第一个例子中，res 是 vector<vector<int>>（二维数组），需要确保每一层都有一个 vector<int> 来存储节点值。

   • 而 rightSideView 中的 res 是 vector<int>（一维数组），只需要存储每一层的最右侧节点值，不需要额外的嵌套结构。

2. 访问方式不同：

   • 在 rightSideView 中，res 的索引 level 直接对应二叉树的层数（从 0 开始）。

   • 当 level == res.size() 时，说明当前层还没有被记录，此时 res.push_back(cur->val) 会直接添加当前节点的值（即该层的最右侧节点）。

   • 如果 level < res.size()，说明该层已经有节点被记录（比如之前已经处理过该层的右子树），就不再重复添加。