C++层序创建一棵二叉树

在C++中，层序创建二叉树通常通过队列数据结构来实现，这种方法也被称为广度优先搜索（Breadth-First Search, BFS）。以下是步骤：

1. 定义一个节点类，包含值和指向左右子节点的指针。

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

2. 创建一个函数，接受一个整数数组作为输入，并返回根节点。数组中的元素按照层次顺序存储。

TreeNode* createLevelOrderTree(vector<int>& levels) {
    if (levels.empty()) return nullptr;

    queue<TreeNode*> q;
    TreeNode* root = new TreeNode(levels[0]);
    q.push(root);

    for (int i = 1; i < levels.size(); ++i) {
        int size = levels[i];
        while (!q.empty() && q.size() > size) {
            q.pop();
        }

        for (int j = 0; j < size; ++j) {
            TreeNode* node = new TreeNode(levels[i * 2 + j]);
            q.push(node);
            if (j < size - 1) {
                q.push(q.front()->left = node->left);
                q.push(q.front()->right = node->right);
            }
        }
    }
    return root;
}

在这个过程中，每次循环我们先处理当前层级的所有节点，然后继续添加下一层的节点。当队列中的节点少于当前层级的节点时，我们就将上一层剩余的节点压入队列。