用C++语言实现用前序遍历算法创建二叉树

在C++中，可以使用递归的方式来实现二叉树的前序遍历并构建一个新的二叉树。前序遍历的顺序通常是根节点 -> 左子树 -> 右子树。下面是一个简单的示例，展示了如何使用结构体表示二叉树节点，并使用函数`buildTreeHelper`来完成前序遍历的构造：

#include <iostream>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 前序遍历辅助函数
TreeNode* buildTreeHelper(const vector<int>& nums, int start, int end) {
    if (start > end)
        return NULL; // 遍历结束

    // 获取当前遍历到的根节点值
    int rootVal = nums[start];
    TreeNode* root = new TreeNode(rootVal);

    // 递归处理左子树和右子树
    root->left = buildTreeHelper(nums, start + 1, findPreOrderIndex(nums, startVal + 1));
    root->right = buildTreeHelper(nums, findPreOrderIndex(nums, startVal + 2), end);

    return root;
}

// 查找前序序列下一个节点的位置
int findPreOrderIndex(vector<int>& nums, int start) {
    for (size_t i = start; i < nums.size(); ++i) {
        if (nums[i] != 0) // 前序序列中，0通常用于分割左右子树
            return i;
    }
    return nums.size(); // 如果遍历完所有元素仍未找到0，说明只有一个节点，返回数组大小作为索引
}

// 主函数示例，输入前序遍历序列构建二叉树
vector<int> preOrderTraversal = {1, 2, 4, 5, 3, 6}; // 假设这是前序遍历结果
TreeNode* root = buildTreeHelper(preOrderTraversal, 0, preOrderTraversal.size() - 1);

在这个例子中，`preOrderTraversal`是给定的前序遍历列表，`buildTreeHelper`会根据这个列表构建一棵完整的二叉树。注意，为了处理前序遍历的特点，我们假设在序列中遇到0就表示子树结束，实际应用中需要根据具体的数据结构调整。