力扣 1008 题解析与 C 代码一、问题解析题目描述给定一个整数数组preorder表示二叉搜索树BST的前序遍历结果请重建该二叉搜索树并返回其根节点。题目保证对于给定的测试用例总能找到一棵二叉搜索树与之对应。核心要点二叉搜索树BST性质对于任意节点其左子树所有节点值 该节点值 右子树所有节点值。前序遍历顺序根节点 → 左子树 → 右子树。重建思路前序遍历的第一个元素是根节点随后连续小于根节点的部分是左子树的前序遍历剩余部分是右子树的前序遍历。递归应用此规则即可重建整棵树。算法步骤取当前区间[start, end]的第一个元素作为根节点值。找到第一个大于根节点值的索引mid该索引将区间划分为左子树[start1, mid-1]和右子树[mid, end]。递归构建左子树和右子树。返回根节点。时间复杂度O(n²)最坏情况如斜树每次需线性扫描划分左右子树。可优化至 O(n)见后续优化方案。空间复杂度O(n)递归栈深度。二、C 代码实现基础递归解法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* bstFromPreorder(vectorint preorder) { return build(preorder, 0, preorder.size() - 1); } private: TreeNode* build(vectorint preorder, int start, int end) { if (start end) return nullptr; // 当前子树的根节点是前序遍历的第一个元素 TreeNode* root new TreeNode(preorder[start]); // 找到第一个大于根节点值的索引划分左右子树 int mid start 1; while (mid end preorder[mid] preorder[start]) { mid; } // 递归构建左右子树 root-left build(preorder, start 1, mid1); root-right build(preorder, mid, end); return root; } };优化解法O(n) 时间复杂度利用单调栈模拟递归过程一次遍历完成构建class Solution { public: TreeNode* bstFromPreorder(vectorint preorder) { if (preorder.empty()) return nullptr; stackTreeNode* stk; TreeNode* root new TreeNode(preorder[0]); stk.push(root); for (int i 1; i preorder.size(); i) { TreeNode* node new TreeNode(preorder[i]); if (preorder[i] stk.top()-val) { // 当前值小于栈顶作为左子节点 stk.top()-left node; } else { // 当前值大于栈顶找到合适的父节点 TreeNode* parent nullptr; while (!stk.empty() preorder[i] stk.top()-val) { parent stk.top(); stk.pop(); } parent-right node; } stk.push(node); } return root; } };三、算法对比特性基础递归解法优化栈解法时间复杂度O(n²)O(n)空间复杂度O(n)O(n)核心思想递归划分左右子树单调栈维护节点关系适用场景数据量较小数据量较大或要求高效代码复杂度简单直观稍复杂但高效四、关键点说明边界处理递归解法中需确保start end时返回nullptr避免无限递归。划分点查找基础解法中线性查找第一个大于根节点的索引是 O(n²) 复杂度的根源。单调栈原理优化解法利用栈保存尚未设置右子树的节点遇到更大值时弹出栈顶直到找到合适父节点确保 BST 性质。相关题目本题与力扣 105从前序与中序遍历构造二叉树思路相似但 BST 性质使得无需中序遍历即可确定左右子树边界。五、测试示例// 测试代码示例 int main() { Solution solution; vectorint preorder {8, 5, 1, 7, 10, 12}; TreeNode* root solution.bstFromPreorder(preorder); // 中序遍历验证BST 中序遍历应为升序 // 预期输出1 5 7 8 10 12 return 0; }参考来源java分割一个整数数组,力扣算法-561.数组拆分-数组-java2019-07-06哈哈哈哈哈哈宋宋在火车上睡觉觉的时候本可爱已经偷偷做了一道PAT的辣鸡简单题这么下去不行啊做的不能一次性全对哪怕简单但是做的太慢了要加快速度啊下周安排下时间刷力扣哈哈哈剑指Offer - 面试题7. 重建二叉树递归PAT 1008 数组元素循环右移问题哈工大算法导论骆吉洲主讲完整课件与核心算法实战解析