c++如何求每一层节点最右边的值

在C++中，如果你想要求解二叉树（每个节点有两个子节点的树结构）的每一层中最右边的节点值，可以使用层次遍历（BFS，即广度优先搜索）算法结合队列数据结构。以下是一个基本的步骤：

1. 定义一个递归结构或者一个辅助函数，用于获取当前层的最后一个节点的索引。

2. 创建一个空的队列，将根节点入队。

3. 初始化一个变量`rightmost`数组来存储每层最右边节点的值，大小等于最大可能层数。

4. 使用循环进行层级遍历，直到队列为空：
a. 当前层的节点数 = 队列长度。
b. 对于每层的每一个节点（从队首开始）：
- 弹出队首元素，并更新右边界值到`rightmost[current_layer]`。
- 将其右子节点（如果存在）和左子节点（如果存在）分别入队，但只加入右侧子节点，因为我们要找的是右边界。
c. 更新当前层`current_layer++`。

5. 最终，`rightmost`数组的每个元素就是对应层的最右边节点的值。

#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int findRightMostInEachLevel(TreeNode* root) {
    if (root == nullptr) return 0;

    std::queue<TreeNode*> q({root});
    std::vector<int> rightmost(root->level + 1, INT_MIN);
    int current_level = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();

            // 更新右边界
            rightmost[current_level] = std::max(rightmost[current_level], node->val);

            // 只添加右子节点到下一层的队列
            if (node->right != nullptr)
                q.push(node->right);
        }

        ++current_level;
    }
    return rightmost;
}

int main() {
    TreeNode* root = ... // 构建你的二叉树
    std::vector<int> result = findRightMostInEachLevel(root);
    for (int val : result) {
        std::cout << "Layer " << result.size() - result.index(val) << ": " << val << std::endl;
    }
    return 0;
}