1. 项目概述今天要和大家分享的是LeetCode上三道关于二叉搜索树(BST)的经典题目669.修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树。这三道题涵盖了BST的构建、修改和转换等核心操作是面试中的高频考点。BST作为一种基础但强大的数据结构具有左子树所有节点值小于根节点、右子树所有节点值大于根节点的特性。这个特性使得BST在搜索、插入、删除等操作上都能达到O(log n)的时间复杂度。这三道题目分别从不同角度考察了对BST特性的理解和应用能力。2. 题目解析与解题思路2.1 669. 修剪二叉搜索树这道题要求我们修剪BST使得所有节点的值都在给定的范围[low, high]内。关键在于理解修剪后仍要保持BST的性质。核心思路如果当前节点值小于low则其左子树所有节点都小于low可以全部舍弃只需处理右子树如果当前节点值大于high则其右子树所有节点都大于high可以全部舍弃只需处理左子树如果当前节点值在范围内则递归处理左右子树2.2 108. 将有序数组转换为二叉搜索树这道题要求我们将一个升序数组转换为高度平衡的BST。高度平衡意味着左右子树的高度差不超过1。核心思路选择数组中间元素作为根节点保证左右子树节点数平衡递归构建左子树和右子树这种方法利用了BST的中序遍历是有序序列的特性2.3 538. 把二叉搜索树转换为累加树这道题要求我们将BST转换为累加树使得每个节点的值变为原树中大于或等于该节点值的所有节点值之和。核心思路利用BST的中序遍历是有序序列的特性采用右-根-左的反向中序遍历维护一个累加变量在遍历过程中不断累加节点值3. 代码实现与详细解析3.1 669. 修剪二叉搜索树实现def trimBST(root, low, high): if not root: return None # 当前节点值小于low修剪左子树 if root.val low: return trimBST(root.right, low, high) # 当前节点值大于high修剪右子树 if root.val high: return trimBST(root.left, low, high) # 当前节点在范围内递归修剪左右子树 root.left trimBST(root.left, low, high) root.right trimBST(root.right, low, high) return root关键点解析递归终止条件遇到空节点直接返回利用BST性质进行剪枝避免不必要的递归调用时间复杂度O(n)空间复杂度O(h)h为树高3.2 108. 将有序数组转换为二叉搜索树实现def sortedArrayToBST(nums): def helper(left, right): if left right: return None # 选择中间位置左边的数字作为根节点 mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)关键点解析使用二分法确保树的高度平衡递归构建左右子树时间复杂度O(n)空间复杂度O(log n)3.3 538. 把二叉搜索树转换为累加树实现def convertBST(root): total 0 def reverseInorder(node): nonlocal total if node: reverseInorder(node.right) total node.val node.val total reverseInorder(node.left) reverseInorder(root) return root关键点解析使用反向中序遍历右-根-左维护一个全局累加变量时间复杂度O(n)空间复杂度O(h)4. 常见问题与优化技巧4.1 修剪BST的边界条件处理常见问题忘记处理空节点情况修剪后没有正确连接子树优化技巧使用迭代法替代递归减少栈空间使用先处理特殊情况节点值小于low或大于high再处理一般情况4.2 有序数组转BST的平衡性保证常见问题选择中间节点时出现偏差导致不平衡递归终止条件设置错误优化技巧对于偶数长度数组可以选择中间偏左或偏右的节点使用循环代替递归构建树4.3 累加树的遍历顺序常见问题使用普通中序遍历导致计算错误累加变量初始化位置错误优化技巧显式使用栈实现反向中序遍历使用Morris遍历实现O(1)空间复杂度5. 复杂度分析与对比题目时间复杂度空间复杂度关键算法669. 修剪BSTO(n)O(h)递归修剪108. 有序数组转BSTO(n)O(log n)二分递归538. BST转累加树O(n)O(h)反向中序从表中可以看出三道题的时间复杂度都是O(n)因为它们都需要访问树中的所有节点。空间复杂度取决于树的形状和使用的算法。6. 实际应用场景修剪BST数据库索引维护、文件系统目录管理有序数组转BST内存数据库初始化、平衡搜索结构构建BST转累加树统计计算、排名系统实现例如在电商平台的商品分类系统中可以使用修剪BST来快速筛选价格区间内的商品在排行榜系统中可以使用累加树来高效计算排名。7. 扩展思考与变种题目修剪普通二叉树如果不保证BST性质该如何修剪构建非平衡BST如果不需要高度平衡如何优化构建过程部分累加树只累加大于某个阈值的节点值如何实现相关变种题目推荐删除BST中的节点BST中的插入操作BST的最小绝对差8. 个人实战经验分享在实际面试和刷题过程中我发现BST相关题目有几个常见陷阱递归终止条件总是忘记处理空节点情况导致栈溢出变量作用域在递归函数中使用全局变量时容易出错树指针操作修剪或修改树结构时容易丢失节点引用我的建议是先画出简单的测试用例手动模拟算法过程使用小数据量测试边界条件在递归函数中添加打印语句方便调试对于BST题目最重要的是充分理解它的有序性质并利用这个性质来优化算法。例如在累加树问题中反向中序遍历就是利用了BST的有序性使得我们可以按从大到小的顺序访问节点。