文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是阿秀《InterviewGuide》中「精选力扣 300 题目之深度优先搜索DFS」系列的一篇经典题解Easy 档位对应面试题 04.02与力扣 108. 将有序数组转换为二叉搜索树为同一道题。文章围绕给定有序整数数组创建高度最小的二叉搜索树这一核心问题完整给出基于递归 DFS 与二分取中的 C 解法并深入讲解为什么取中间元素作根、为什么右边界必须传nums.size() - 1等易错细节最终给出复杂度分析与仓库内的延伸练习路径。读完本文你将掌握有序序列 → 平衡二叉搜索树这一高频面试模型的推导方法与标准代码模板。题目背景与考点定位这道题收录在 13-DFS 专题 的 Easy 分档中与 104. 二叉树的最大深度、111. 二叉树的最小深度 同属二叉树 递归的基础题型是校招、社招面试中出镜率极高的入门级压轴热身题。它在算法上同时踩中了两个重要考点二叉搜索树BST的性质对于任意节点左子树所有节点值均小于该节点右子树所有节点值均大于该节点对 BST 做中序遍历得到的结果恰好是升序序列。递归分治DFS与二分思想的结合把有序数组视为 BST 中序遍历的结果反过来通过取中建树完成从线性结构到树形结构的重建。仓库中与之同源的知识点还包括 14-树 专题 下的 230. 二叉搜索树中第 K 小的元素、面试题 33. 二叉搜索树的后序遍历序列 等建议按构造本题→ 遍历230→ 校验33的顺序串起来复习。题目描述给定一个有序整数数组其中的元素各不相同且按升序排列编写一个算法创建一棵高度最小的二叉搜索树。示例给定有序数组: [-10,-3,0,5,9] 一个可能的答案是[0,-3,9,-10,null,5] 它表示的树结构如下 0 / \ -3 9 / / -10 5注意题目只说一个可能的答案这是因为当子数组长度为偶数时中间位置左中位或右中位的选择存在两种等价写法两种结果都满足高度最小的要求。核心思路为什么取中间、递归分治能保证高度最小要让一棵包含 n 个节点的二叉搜索树高度最小直觉上应当让树的形态尽可能扁——也就是让左右子树尽量均衡。由于输入数组已有序数组中任一位置k左侧的k个元素天然小于nums[k]、右侧的n-k-1个元素天然大于nums[k]因此任意位置都可以作为根且左右两侧天然构成 BST 的左右子树候选。问题随之而来选哪个位置做根才能让树最矮若选nums[0]或nums[n-1]做根一侧子树为空、另一侧退化为链状高度为n若每次都选当前区间的中间元素做根则左、右两个子区间的大小差不超过 1整棵树左右子树高度差不超过 1恰好是一棵高度平衡的二叉搜索树高度被压到⌈log₂(n1)⌉级别即最小高度。这个过程本质上是分治每次取中位数将区间一分为二然后分别对左半区间、右半区间递归执行同样的操作直到区间为空。这也是 DFS深度优先搜索在二叉树构造问题中的典型应用——递归的深入顺序是先沿着左子树一路建到叶子再回溯建右子树。C 题解递归 DFS 二分取中原题解完整代码如下来自 面试题04.02.最小高度树.md/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: TreeNode* dfs(vectorint nums, int l, int r) { if (l r) return NULL; int mid (l r) 1; TreeNode* root new TreeNode(nums[mid]); root-left dfs(nums, l, mid - 1); root-right dfs(nums, mid 1, r); return root; } public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.size() 0) return NULL; return dfs(nums, 0, nums.size() - 1); } };对核心代码做逐段拆解私有递归函数dfs(nums, l, r)表示用数组nums中下标[l, r]这一段升序子区间构造一棵最小高度 BST。递归的三段式结构清晰直观终止条件if (l r) return NULL;区间为空时返回空节点建根int mid (l r) 1;取当前区间中间位置 1等价于除以 2向下取整用nums[mid]创建根节点递归建左右子树root-left dfs(nums, l, mid - 1);与root-right dfs(nums, mid 1, r);分别处理左右两个子区间返回后作为当前根节点的左右孩子。公有入口sortedArrayToBST(nums)先处理空数组的特殊情况再以[0, nums.size()-1]作为完整区间启动递归。以示例[-10,-3,0,5,9]手动推演一遍递归过程根l0, r4mid2根节点值为0左子树区间[0,1]mid0节点值为-10其右孩子为区间[1,1]建出的-3右子树区间[3,4]mid3节点值为5其左孩子为区间[4,4]建出的9。最终得到的树与题目示例完全一致且任意节点均满足左 根 右的 BST 约束同时整棵树左右均衡、高度最小。关键细节为什么右边界必须是 nums.size() - 1这是本题最容易写错的一个点原文档也专门做了标注。若把入口误写成return dfs(nums, 0, nums.size()); // 错误写法那么在mid (l r) 1计算中r会指向最后一个元素之后的越界位置。虽然nums.size()本身不会立即触发越界因为vector::operator[]不做边界检查属于未定义行为但会出现两类问题当递归到l r即r nums.size()时mid会等于nums.size()nums[mid]访问越界逻辑上[l, r]区间也多包含了一个不存在的元素导致区间划分错乱。正确的写法是把右边界闭区间收在nums.size() - 1保证mid永远落在合法下标范围内。同理在递归内部调用时也要严格遵守闭区间语义左半区间是[l, mid-1]右半区间是[mid1, r]从而确保递归最终能通过l r正确收敛、不会漏建节点也不会重复建节点。顺带一提在偶数长度的区间上例如[0,1](l r) 1取到的是左中位下标0因此左子树可能比右子树少一个节点若想取右中位可写成(l r 1) 1两种写法生成的都是合法的最小高度 BST。边界情况与复杂度分析边界情况空数组nums.size() 0时直接返回NULL避免对空容器取下标单元素数组l r创建单个节点后左右递归均以l r立即返回NULL偶数长度数组取左中位建根左右子树节点数差为 1仍保持高度最小。复杂度分析时间复杂度O(n)。每个数组元素恰好被访问一次并创建一个树节点递归调用总次数为 2n 级别空间复杂度O(log n)。递归深度等于树高即最小高度 BST 的高度⌈log₂(n1)⌉这是递归栈占用的空间若将递归改为显式栈的迭代写法思路完全相同只是不再占用系统调用栈。从仓库中 104. 二叉树的最大深度 的解法可以对照看出这道题用递归建树而深度类题目用递归统计树高二者互为正向构造与逆向度量的关系——若对你构造出的树调用一次maxDepth得到的深度恰好就是理论最小高度可以用这种方式自测构造结果是否正确。变式与延伸从最小高度到平衡二叉搜索树系列掌握有序数组 → 最小高度 BST之后可以顺藤摸瓜延伸到仓库中同一知识簇的其他题目力扣 110. 平衡二叉树判断一棵树是否左右子树高度差不超过 1。本题构造出的树天然满足该判定是构造平衡树的逆命题力扣 98. 验证二叉搜索树校验树的 BST 约束左 根 右与本题构造过程的约束互为验证230. 二叉搜索树中第 K 小的元素对 BST 做中序遍历取第 k 个元素本质上利用了BST 中序 升序这一与本题相同的核心性质面试题 33. 二叉搜索树的后序遍历序列已知后序遍历反推 BST 是否合法与本题已知中序有序数组正推 BST构成构造与校验的完整闭环。延伸思考如果输入不再是有序数组而是任意数组则需要先排序O(n log n)再套用本题模板如果输入是链表而非数组则取中间节点需要快慢指针定位力扣 109 正是这道题的链表版本。本题的递归模板稍作改动即可复用于上述全部场景。仓库配套资源与刷题路径本题题解docs/notes/03-hunting_job/03-algorithm/03-leetcode/13-DFS/easy/面试题04.02.最小高度树.mdDFS 专题目录Easy/Medium/Hard 分档导航docs/notes/03-hunting_job/03-algorithm/03-leetcode/13-DFS/introduce.md同档位姊妹题104. 二叉树的最大深度、111. 二叉树的最小深度、面试题 55-I. 二叉树的深度树专题整体导航docs/notes/03-hunting_job/03-algorithm/03-leetcode/14-树/introduce.md刷题建议先独立写出递归取中建树的完整模板并背下三段式结构终止条件、建根、左右递归再用 110 与 98 两道题检验对平衡与BST 约束的理解最后用 230 题打通BST 中序 升序这一贯穿始终的核心性质。本题虽标记为 Easy但它是众多中等、困难二叉树题的构造基石值得反复刷熟。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐doocs/leetcode 题解精讲面试题 04.02 最小高度树——有序数组递归构建最矮二叉搜索树doocs/leetcode 题解精讲面试题 04.02 最小高度树——有序数组递归构建最矮二叉搜索树 给定一个元素互不相同、按升序排列的整数数组如何构造一示例工程教程面试题 04.02 最小高度树从有序数组构造高度平衡 BST 的递归解法详解doocs/leetcode面试题 04.02 最小高度树从有序数组构造高度平衡 BST 的递归解法详解doocs/leetcode 给定一个元素各不相同且按升序排列的整数数组如何示例工程教程如何从有序数组构建最小高度二叉搜索树终极技术指南与实战技巧 如何从有序数组构建最小高度二叉搜索树终极技术指南与实战技巧 在技术面试和算法竞赛中 从有序数组构建最小高度二叉搜索树 是一个经典且重要的算法问题。这个示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考