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

19339201706

一、题目理解

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

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

二、解题思路

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

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

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

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

三、C++代码实现

1. // 定义二叉树节点结构体
   
2. struct TreeNode {
   
3.     int val;
   
4.     TreeNode left;
   
5.     TreeNode right;
   
6.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   
7. };
   
8. 
   
9. // 递归函数，用于构造二叉树
   
10. TreeNode buildTree(vector& preorder, int& index) {
    
11.     if (index >= preorder.size()) return nullptr; // 如果索引超出范围，返回空指针
    
12.     int value = preorder[index]; // 当前根节点的值
    
13.     TreeNode root = new TreeNode(value); // 创建根节点
    
14.     index++; // 移动到下一个元素
    
15. 
    
16.     // 构建左子树
    
17.     root->left = buildTree(preorder, index);
    
18. 
    
19.     // 构建右子树
    
20.     root->right = buildTree(preorder, index);
    
21. 
    
22.     return root; // 返回根节点
    
23. }
    
24. 
    
25. // 主函数，用于调用递归函数
    
26. TreeNode bstFromPreorder(vector& preorder) {
    
27.     int index = 0; // 初始化索引
    
28.     return buildTree(preorder, index); // 调用递归函数
    
29. }

复制代码

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