力扣1008题 解题思路和步骤 C++实现带注释
https://dajuwangluo.cn/zb_users/upload/2025/05/202505231747982205547816.jpg一、题目理解力扣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; // 当前根节点的值
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); // 调用递归函数
}转自：力扣1008题 解题思路和步骤 C++实现带注释
页:
[1]