LC.1008 ｜ 前序遍历构造二叉搜索树 ｜ 树 ｜ 递归遍历

输入：
一个整数数组preorder，代表二叉搜索树的先序遍历结果。

要求：
根据给定的先序遍历还原出二叉搜索树（BST）。
BST 的性质是：对于任意节点，左子树所有节点值 < 当前节点值 < 右子树所有节点值。

输出：
构造出的二叉搜索树的根节点TreeNode*。

思路：

本题解采用了直观的“递归 + 分治”策略，利用了二叉搜索树（BST）的核心性质来切分数据。

1. 确定根节点：
   前序遍历的第一个元素永远是当前子树的根节点。我们首先取出pre[0]创建根节点tmp。

2. 划分子集（分治）：
   根据 BST 的性质，比根节点小的元素属于左子树，比根节点大的元素属于右子树。
   我们遍历pre数组中剩余的元素：

   • 若元素值小于pre[0]，放入preleft数组。
   • 若元素值大于pre[0]，放入preright数组。

3. 递归构建：

   • tmp->left= 递归处理preleft。
   • tmp->right= 递归处理preright。
   • 如果传入的数组为空，说明该分支已到达叶子节点下方，返回nullptr。

优化：
当前解法在每一层递归都创建了新的vector，这会增加额外的空间开销和拷贝时间。更优的做法是传递原始数组的索引范围（start,end）或者使用“上限值控制法”来避免数组拷贝，但在逻辑理解上，当前的解法是符合直觉的。

复杂度：

• 时间复杂度：O(N^2)
  • 在最坏情况下（例如链状树），每一层递归都需要遍历剩余所有元素并进行拷贝，导致总操作次数接近 N + (N-1) + … + 1。
• 空间复杂度：O(N^2)
  • 每一层递归都创建了新的vector存储子数组，导致大量的额外空间消耗。

classSolution{public:TreeNode*bstFromPreorder(vector<int>&preorder){returntree(preorder);}TreeNode*tree(vector<int>pre){if(pre.size()==0){returnnullptr;}TreeNode*tmp=newTreeNode(pre[0]);vector<int>preleft,preright;for(inti=1;i<pre.size();i++){if(pre[i]>pre[0]){preright.push_back(pre[i]);}else{preleft.push_back(pre[i]);}}tmp->left=tree(preleft);tmp->right=tree(preright);returntmp;}};