满二叉树C++前序遍历构造树

满二叉树是一种特殊的二叉树，其中每个节点都有0个或2个子节点，并且所有层级都是完全填充的。对于满二叉树的前序遍历构造树，前序遍历的顺序通常是“根-左-右”，即先访问根节点，然后遍历左子树，最后遍历右子树。

C++中，可以按照这个顺序来构建满二叉树。首先，我们需要保存一个队列用于存储遍历过程中的节点，因为前序遍历时根节点总是第一个出栈。以下是基本步骤：

1. 定义一个结构体或类表示树的节点，包含值和左右子节点指针。
2. 创建一个空的根节点。
3. 接收前序遍历序列作为输入，例如`vector<int> preorder`。
4. 初始化队列，将根节点入队。
5. 当队列非空时：
a. 出队当前节点，将其添加到结果树的对应位置。
b. 如果当前节点的右子节点在前序序列中，找到它的索引并减一（因为序列是从0开始的），然后将该节点入队。
c. 同理，如果当前节点有左子节点，也找到其索引并减一，将左子节点入队。

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

vector<TreeNode*> buildTree(vector<int>& preorder) {
    if (preorder.empty()) return {};

    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> s({root});
    int i = 1;

    while (!s.empty() && i < preorder.size()) {
        TreeNode* node = s.top();
        s.pop();

        if (i < preorder.size() && preorder[i] == node->val) {
            // 找到右子节点
            node->right = new TreeNode(preorder[i + 1]);
            s.push(node->right);
            i += 2;
        } else {
            // 左子节点已经在前面处理过了，直接出队等待处理
            assert(i < preorder.size());
            node->left = s.top(); // 右子节点已经出队，所以左子节点还在栈顶
            s.pop();
        }
    }

    return {root};
}