用c++拓展先序遍历还原满二叉树

下面是用 C++ 实现拓展先序遍历还原满二叉树的代码：

#include <iostream>
#include <string>
using namespace std;

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

TreeNode* buildTree(string& s, int& index)
{
    if (index >= s.size() || s[index] == '#') {
        return nullptr;
    }
    int val = s[index] - '0';
    TreeNode* root = new TreeNode(val);
    index++;
    root->left = buildTree(s, index);
    index++;
    root->right = buildTree(s, index);
    return root;
}

void inorderTraversal(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main()
{
    string s = "123##4##56##";
    int index = 0;
    TreeNode* root = buildTree(s, index);
    inorderTraversal(root);
    cout << endl;
    return 0;
}

以上代码中，我们首先定义了一个 TreeNode 结构体，用于表示二叉树节点信息。我们还定义了一个 buildTree 函数，用于构建二叉树。该函数以拓展先序遍历序列作为输入，同时还维护了一个 index 变量，用于表示当前处理的字符下标。函数返回构建好的原二叉树的根节点。

具体地，我们首先判断当前字符是否为 '#'，如果是则返回空节点。接着，我们从输入序列中获取当前节点的值，构建当前节点，并递归处理其左右子树。最终，我们返回构建好的原二叉树的根节点。

在 main 函数中，我们定义了一个拓展先序遍历序列作为输入，然后调用 buildTree 函数构建原二叉树，并采用中序遍历的方式输出二叉树节点的值，以验证还原结果是否正确。