力扣1008题 解题思路和步骤 C++实现带注释

一、题目理解

力扣1008题要求我们根据给定的二叉树的前序遍历结果构造出一棵二叉树。前序遍历是指先访问根节点，递归地遍历左子树，递归地遍历右子树。

关键词：二叉树，前序遍历，构造，C++实现

二、解题思路

解题思路主要分为以下几步：

1. 确定根节点：前序遍历的第一个元素一定是根节点。

2. 构建左右子树：根据根节点，将剩余的前序遍历序列分割为左右子树两部分。

3. 递归实现：对左右子树递归执行上述步骤，直到所有节点都被创建。

三、C++代码实现

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

// 递归函数，用于构造二叉树
TreeNode buildTree(vector& preorder, int& index) {
    if (index >= preorder.size()) return nullptr; // 如果索引超出范围，返回空指针
    int value = preorder[index]; // 当前根节点的值
    TreeNode root = new TreeNode(value); // 创建根节点
    index++; // 移动到下一个元素

    // 构建左子树
    root->left = buildTree(preorder, index);

    // 构建右子树
    root->right = buildTree(preorder, index);

    return root; // 返回根节点
}

// 主函数，用于调用递归函数
TreeNode bstFromPreorder(vector& preorder) {
    int index = 0; // 初始化索引
    return buildTree(preorder, index); // 调用递归函数
}