LeetCodehot 力扣热题100 二叉树的右视图
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans; // 用于存储从右侧看每一层的节点值
int layer = 1; // 从根节点开始，层级是1
rightSideViewfunction(root, layer, ans); // 调用辅助函数进行递归遍历
return ans; // 返回结果
}
void rightSideViewfunction(TreeNode *root, int layer, vector<int> &ans) {
if (root != nullptr) { // 如果当前节点为空，返回
// 如果当前层级还没有记录节点值，则将当前节点的值加入答案
if (layer > ans.size())
ans.push_back(root->val); // 把当前节点值加入答案
// 递归遍历右子树，先遍历右子树保证右边的节点先被访问到
rightSideViewfunction(root->right, layer + 1, ans);
// 递归遍历左子树
rightSideViewfunction(root->left, layer + 1, ans);
}
}
};下面是对你提供的 C++ 代码的详细解释、注释和思路解析。
题目思路
这个代码的目标是给定一个二叉树，返回从右侧看每一层的节点值。也就是说，我们需要按层级遍历树，记录每一层最右边的节点。
思路解析
1. 层级遍历：我们需要遍历每一层的节点。由于问题要求“从右侧看”，我们可以先遍历右子树，然后是左子树，这样就能保证每次遍历到的第一个节点是右侧的节点。
2. 递归遍历：采用递归深度优先遍历（DFS）来解决。每次递归中，判断当前的层级（layer）是否已经有节点被记录。如果没有，则把当前节点值加入答案。
3. 记录答案：答案是一个按层级从上到下、从右到左的节点值列表。
好的，下面我会更详细地解释这段代码的运行步骤，逐步模拟递归过程，并结合一个例子来说明每个步骤是如何执行的。
假设我们有如下的二叉树：
1
/ \
2 3
\ \
5 4
我们从右侧视角来看每一层的节点，最终输出 [1, 3, 4]，即从右侧看每一层的最右节点。
递归调用的详细步骤
1. 初始调用：
• rightSideView(root) 被调用时，root 是树的根节点，值为 1。接着它调用了辅助函数 rightSideViewfunction(root, 1, ans)，layer 初始化为 1，ans 是一个空的 vector<int>。
2. 第 1 层：
• 当前节点：root = 1，layer = 1。
• 进入 rightSideViewfunction 函数：
• root 不是 nullptr，继续判断层级。
• 当前层级 1 > ans.size() = 0，说明第 1 层的节点值还没有被记录，所以把 1 加入 ans。
• ans = [1]。
• 递归调用右子树：rightSideViewfunction(root->right, 2, ans)，root->right 是节点 3，layer = 2。
3. 第 2 层（右子树）：
• 当前节点：root = 3，layer = 2。
• 进入 rightSideViewfunction 函数：
• root 不是 nullptr，继续判断层级。
• 当前层级 2 > ans.size() = 1，说明第 2 层的节点值还没有被记录，所以把 3 加入 ans。
• ans = [1, 3]。
• 递归调用右子树：rightSideViewfunction(root->right, 3, ans)，root->right 是节点 4，layer = 3。
4. 第 3 层（右子树）：
• 当前节点：root = 4，layer = 3。
• 进入 rightSideViewfunction 函数：
• root 不是 nullptr，继续判断层级。
• 当前层级 3 > ans.size() = 2，说明第 3 层的节点值还没有被记录，所以把 4 加入 ans。
• ans = [1, 3, 4]。
• 由于节点 4 没有左右子树，递归返回到上一层。
5. 回到第 2 层（继续遍历左子树）：
• 当前节点：root = 3，layer = 2。
• 继续递归遍历左子树：rightSideViewfunction(root->left, 3, ans)，root->left 是 nullptr，直接返回。
6. 回到第 1 层（继续遍历左子树）：
• 当前节点：root = 1，layer = 1。
• 继续递归遍历左子树：rightSideViewfunction(root->left, 2, ans)，root->left 是节点 2，layer = 2。
7. 第 2 层（左子树）：
• 当前节点：root = 2，layer = 2。
• 进入 rightSideViewfunction 函数：
• root 不是 nullptr，继续判断层级。
• 当前层级 2 ≤ ans.size() = 3，说明第 2 层的节点值已经记录了，所以不再加入 ans。
• ans = [1, 3, 4]，没有变化。
• 递归调用右子树：rightSideViewfunction(root->right, 3, ans)，root->right 是节点 5，layer = 3。
8. 第 3 层（右子树）：
• 当前节点：root = 5，layer = 3。
• 进入 rightSideViewfunction 函数：
• root 不是 nullptr，继续判断层级。
• 当前层级 3 ≤ ans.size() = 3，说明第 3 层的节点值已经记录了，所以不再加入 ans。
• ans = [1, 3, 4]，没有变化。
• 由于节点 5 没有左右子树，递归返回到上一层。
9. 回到第 2 层（继续遍历左子树）：
• 当前节点：root = 2，layer = 2。
• 继续递归遍历左子树：rightSideViewfunction(root->left, 3, ans)，root->left 是 nullptr，直接返回。
10. 结束：
• 所有节点都已经被遍历过，递归完成。
最终结果
经过以上递归步骤后，最终的 ans 数组是 [1, 3, 4]，即从右侧看每一层的最右边的节点值。
总结
通过这段代码的递归过程，我们能够实现从右侧查看每一层的最右节点的功能。递归的关键在于：
• 使用 layer 来表示当前层级。
• 从右子树先行遍历，这样保证了每次访问的第一个节点是右侧的节点。
• 使用 ans.size() 判断每一层是否已经有节点值记录，从而确保每层只有最右边的节点值被记录。
• 时间复杂度：O(n)，其中 n 是树的节点数。每个节点都被访问一次。
• 空间复杂度：O(h)，其中 h 是树的高度，用于递归栈的空间。如果树是平衡的，空间复杂度为 O(log n)，如果是单链表形状的树，空间复杂度为 O(n)。