输入：
一个整数数组preorder，代表二叉搜索树的先序遍历结果。
要求：
根据给定的先序遍历还原出二叉搜索树（BST）。
BST 的性质是：对于任意节点，左子树所有节点值 < 当前节点值 < 右子树所有节点值。
输出：
构造出的二叉搜索树的根节点TreeNode*。
思路：
本题解采用了直观的“递归 + 分治”策略，利用了二叉搜索树（BST）的核心性质来切分数据。
确定根节点：
前序遍历的第一个元素永远是当前子树的根节点。我们首先取出pre[0]创建根节点tmp。划分子集（分治）：
根据 BST 的性质，比根节点小的元素属于左子树，比根节点大的元素属于右子树。
我们遍历pre数组中剩余的元素：- 若元素值小于
pre[0]，放入preleft数组。 - 若元素值大于
pre[0]，放入preright数组。
- 若元素值小于
递归构建：
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;}};
