1. 二叉树操作实战三部曲今天咱们来啃三道LeetCode二叉树相关的经典题目这三题看似独立实则环环相扣完整覆盖了BST二叉搜索树的增删改查全生命周期操作。作为刷过300二叉树题目的老司机我把这三道题放在一起讲解因为它们恰好展示了BST从创建到改造的完整技术链条。先快速过一下题目概要669题是BST修剪手术需要保留指定范围内的节点108题是BST的构建过程从有序数组生成平衡BST538题是BST的变形记将普通BST改造成累加树这三道题在面试中出现的频率相当高特别是108题作为BST构建的标准解法我在字节和腾讯的面试中都被考察过。下面我们就从最基础的BST特性开始逐步拆解这三道题的解题思路。2. 669. 修剪二叉搜索树2.1 问题重述与特性分析给定一个BST的根节点root同时给定边界[low, high]要求修剪树使得所有节点的值都在这个范围内。修剪后的树仍然要保持BST的性质。BST的核心特性大家应该都清楚左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也都是BST这个特性决定了我们的修剪策略当前节点值 low整个左子树都可以丢弃但右子树可能有合格节点当前节点值 high整个右子树都可以丢弃但左子树可能有合格节点当前节点值在范围内需要递归处理左右子树2.2 递归解法实现我们先来看最直观的递归解法def trimBST(root, low, high): if not root: return None # 当前节点值小于下限抛弃左子树 if root.val low: return trimBST(root.right, low, 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这个解法的时间复杂度是O(N)空间复杂度在最坏情况下树退化为链表也是O(N)。关键点修剪BST不是简单的删除节点而是要考虑子树中可能存在的合格节点。比如当root.val low时不能直接返回None而是要继续检查右子树。2.3 迭代解法优化递归解法虽然直观但在实际工程中可能会面临栈溢出的风险。我们来看迭代解法def trimBST(root, low, high): # 先找到合格的根节点 while root and (root.val low or root.val high): root root.right if root.val low else root.left if not root: return None # 修剪左子树 node root while node.left: if node.left.val low: node.left node.left.right else: node node.left # 修剪右子树 node root while node.right: if node.right.val high: node.right node.right.left else: node node.right return root迭代解法避免了递归的栈开销更适合处理大规模树结构。不过代码逻辑稍复杂需要仔细处理指针的修改。3. 108. 将有序数组转换为二叉搜索树3.1 问题理解与转化这道题要求我们将一个按照升序排列的有序数组转换为一棵高度平衡的BST。高度平衡的意思是每个节点的两个子树高度差不超过1。关键观察点BST的中序遍历结果就是有序数组要构建平衡BST应该总是选择中间元素作为根节点这实际上是一个分治算法的经典应用场景。3.2 分治递归实现标准解法如下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(logN)这是递归栈的深度。实用技巧在实际面试中面试官可能会问为什么选择中间偏左或中间偏右的节点作为根节点。其实对于偶数长度的数组选择中间偏左或偏右都可以保证平衡只是生成的树结构会稍有不同。3.3 迭代解法探索虽然递归解法简洁但我们也应该了解迭代解法def sortedArrayToBST(nums): if not nums: return None root TreeNode(0) # 临时值 stack [(0, len(nums) - 1, root)] while stack: left, right, node stack.pop() mid (left right) // 2 node.val nums[mid] if left mid - 1: node.left TreeNode(0) stack.append((left, mid - 1, node.left)) if mid 1 right: node.right TreeNode(0) stack.append((mid 1, right, node.right)) return root迭代解法使用显式栈来模拟递归过程避免了递归的函数调用开销。这在处理极大数组时可能更有优势。4. 538. 把二叉搜索树转换为累加树4.1 问题理解与转化这道题要求我们将BST转换为累加树使得每个节点的值变成原树中大于或等于该节点值的所有节点值之和。关键观察点BST的中序遍历是升序序列累加树相当于逆中序遍历右-根-左的累加和4.2 递归解法实现我们可以利用逆中序遍历的特性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)H是树的高度。常见错误初学者可能会尝试先中序遍历得到所有节点然后计算累加和再赋值。这样虽然也能得到正确结果但需要额外的O(N)空间存储节点不如直接在遍历过程中累加高效。4.3 迭代解法优化我们同样可以提供迭代版本def convertBST(root): total 0 stack [] node root while stack or node: while node: stack.append(node) node node.right node stack.pop() total node.val node.val total node node.left return root迭代版本使用显式栈来模拟递归过程更适合处理深度很大的树结构。5. 综合应用与实战技巧5.1 三道题的共性分析虽然这三道题看似独立但它们实际上展示了BST操作的完整链条108题从数据构建BST创建669题对BST进行修剪修改538题对BST进行转换变形理解这三道题的解法可以帮助我们掌握BST的核心操作模式。5.2 二叉树遍历的统一框架通过这三道题我们可以总结出二叉树问题的一个通用解决框架确定遍历顺序前序、中序、后序在适当的位置插入处理逻辑考虑使用递归或迭代实现优化空间和时间复杂度5.3 面试实战建议在面试中遇到BST相关问题时建议按照以下步骤思考明确BST的特性中序遍历有序根据问题需求确定遍顺序考虑递归和迭代两种实现分析时间空间复杂度讨论可能的优化方向我在面试候选人时最看重的不是能否写出完美代码而是能否清晰地解释解题思路和复杂度分析。这三道题都是考察这些能力的绝佳素材。6. 常见问题与调试技巧6.1 边界条件处理在实现这些算法时有几个常见的边界条件需要注意空树处理root为None单节点树完全左倾或右倾的树重复元素处理虽然BST一般不包含重复元素6.2 调试技巧当你的代码出现问题时可以尝试以下调试方法手动构造一个小型测试用例3-5个节点在纸上画出树的结构逐步模拟代码执行过程添加打印语句输出关键变量值例如对于538题可以在reverseInorder函数中添加print(f访问节点{node.val}, 当前累加和{total})6.3 性能优化方向对于大规模树结构可以考虑以下优化使用迭代代替递归避免栈溢出对于修剪操作可以提前终止不必要的递归对于累加树转换可以尝试并行处理右子树7. 扩展思考与实际应用7.1 实际工程应用这些算法在实际工程中有广泛的应用场景数据库索引的维护B树/B树操作文件系统的目录结构管理游戏中的场景树管理机器学习中的决策树算法7.2 变种问题探索基于这三道题可以延伸出许多有趣的变种问题如何修剪普通二叉树非BST如果输入数组有重复元素如何构建BST如何将累加树转换回原始BST如何在修剪的同时统计被删除的节点数量7.3 进阶学习建议想要深入掌握二叉树算法我推荐以下学习路径熟练掌握各种遍历方式前中后序层次遍历理解递归和迭代的转换关系学习常见的树形DP问题研究平衡二叉树的维护AVL树红黑树我在刚开始学习二叉树时曾经花费两周时间专门练习各种遍历算法直到能够闭眼写出无bug的代码。这种基础训练在后来的面试和工程实践中带来了巨大的回报。
LeetCode二叉树实战：BST增删改查全解析
1. 二叉树操作实战三部曲今天咱们来啃三道LeetCode二叉树相关的经典题目这三题看似独立实则环环相扣完整覆盖了BST二叉搜索树的增删改查全生命周期操作。作为刷过300二叉树题目的老司机我把这三道题放在一起讲解因为它们恰好展示了BST从创建到改造的完整技术链条。先快速过一下题目概要669题是BST修剪手术需要保留指定范围内的节点108题是BST的构建过程从有序数组生成平衡BST538题是BST的变形记将普通BST改造成累加树这三道题在面试中出现的频率相当高特别是108题作为BST构建的标准解法我在字节和腾讯的面试中都被考察过。下面我们就从最基础的BST特性开始逐步拆解这三道题的解题思路。2. 669. 修剪二叉搜索树2.1 问题重述与特性分析给定一个BST的根节点root同时给定边界[low, high]要求修剪树使得所有节点的值都在这个范围内。修剪后的树仍然要保持BST的性质。BST的核心特性大家应该都清楚左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也都是BST这个特性决定了我们的修剪策略当前节点值 low整个左子树都可以丢弃但右子树可能有合格节点当前节点值 high整个右子树都可以丢弃但左子树可能有合格节点当前节点值在范围内需要递归处理左右子树2.2 递归解法实现我们先来看最直观的递归解法def trimBST(root, low, high): if not root: return None # 当前节点值小于下限抛弃左子树 if root.val low: return trimBST(root.right, low, 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这个解法的时间复杂度是O(N)空间复杂度在最坏情况下树退化为链表也是O(N)。关键点修剪BST不是简单的删除节点而是要考虑子树中可能存在的合格节点。比如当root.val low时不能直接返回None而是要继续检查右子树。2.3 迭代解法优化递归解法虽然直观但在实际工程中可能会面临栈溢出的风险。我们来看迭代解法def trimBST(root, low, high): # 先找到合格的根节点 while root and (root.val low or root.val high): root root.right if root.val low else root.left if not root: return None # 修剪左子树 node root while node.left: if node.left.val low: node.left node.left.right else: node node.left # 修剪右子树 node root while node.right: if node.right.val high: node.right node.right.left else: node node.right return root迭代解法避免了递归的栈开销更适合处理大规模树结构。不过代码逻辑稍复杂需要仔细处理指针的修改。3. 108. 将有序数组转换为二叉搜索树3.1 问题理解与转化这道题要求我们将一个按照升序排列的有序数组转换为一棵高度平衡的BST。高度平衡的意思是每个节点的两个子树高度差不超过1。关键观察点BST的中序遍历结果就是有序数组要构建平衡BST应该总是选择中间元素作为根节点这实际上是一个分治算法的经典应用场景。3.2 分治递归实现标准解法如下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(logN)这是递归栈的深度。实用技巧在实际面试中面试官可能会问为什么选择中间偏左或中间偏右的节点作为根节点。其实对于偶数长度的数组选择中间偏左或偏右都可以保证平衡只是生成的树结构会稍有不同。3.3 迭代解法探索虽然递归解法简洁但我们也应该了解迭代解法def sortedArrayToBST(nums): if not nums: return None root TreeNode(0) # 临时值 stack [(0, len(nums) - 1, root)] while stack: left, right, node stack.pop() mid (left right) // 2 node.val nums[mid] if left mid - 1: node.left TreeNode(0) stack.append((left, mid - 1, node.left)) if mid 1 right: node.right TreeNode(0) stack.append((mid 1, right, node.right)) return root迭代解法使用显式栈来模拟递归过程避免了递归的函数调用开销。这在处理极大数组时可能更有优势。4. 538. 把二叉搜索树转换为累加树4.1 问题理解与转化这道题要求我们将BST转换为累加树使得每个节点的值变成原树中大于或等于该节点值的所有节点值之和。关键观察点BST的中序遍历是升序序列累加树相当于逆中序遍历右-根-左的累加和4.2 递归解法实现我们可以利用逆中序遍历的特性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)H是树的高度。常见错误初学者可能会尝试先中序遍历得到所有节点然后计算累加和再赋值。这样虽然也能得到正确结果但需要额外的O(N)空间存储节点不如直接在遍历过程中累加高效。4.3 迭代解法优化我们同样可以提供迭代版本def convertBST(root): total 0 stack [] node root while stack or node: while node: stack.append(node) node node.right node stack.pop() total node.val node.val total node node.left return root迭代版本使用显式栈来模拟递归过程更适合处理深度很大的树结构。5. 综合应用与实战技巧5.1 三道题的共性分析虽然这三道题看似独立但它们实际上展示了BST操作的完整链条108题从数据构建BST创建669题对BST进行修剪修改538题对BST进行转换变形理解这三道题的解法可以帮助我们掌握BST的核心操作模式。5.2 二叉树遍历的统一框架通过这三道题我们可以总结出二叉树问题的一个通用解决框架确定遍历顺序前序、中序、后序在适当的位置插入处理逻辑考虑使用递归或迭代实现优化空间和时间复杂度5.3 面试实战建议在面试中遇到BST相关问题时建议按照以下步骤思考明确BST的特性中序遍历有序根据问题需求确定遍顺序考虑递归和迭代两种实现分析时间空间复杂度讨论可能的优化方向我在面试候选人时最看重的不是能否写出完美代码而是能否清晰地解释解题思路和复杂度分析。这三道题都是考察这些能力的绝佳素材。6. 常见问题与调试技巧6.1 边界条件处理在实现这些算法时有几个常见的边界条件需要注意空树处理root为None单节点树完全左倾或右倾的树重复元素处理虽然BST一般不包含重复元素6.2 调试技巧当你的代码出现问题时可以尝试以下调试方法手动构造一个小型测试用例3-5个节点在纸上画出树的结构逐步模拟代码执行过程添加打印语句输出关键变量值例如对于538题可以在reverseInorder函数中添加print(f访问节点{node.val}, 当前累加和{total})6.3 性能优化方向对于大规模树结构可以考虑以下优化使用迭代代替递归避免栈溢出对于修剪操作可以提前终止不必要的递归对于累加树转换可以尝试并行处理右子树7. 扩展思考与实际应用7.1 实际工程应用这些算法在实际工程中有广泛的应用场景数据库索引的维护B树/B树操作文件系统的目录结构管理游戏中的场景树管理机器学习中的决策树算法7.2 变种问题探索基于这三道题可以延伸出许多有趣的变种问题如何修剪普通二叉树非BST如果输入数组有重复元素如何构建BST如何将累加树转换回原始BST如何在修剪的同时统计被删除的节点数量7.3 进阶学习建议想要深入掌握二叉树算法我推荐以下学习路径熟练掌握各种遍历方式前中后序层次遍历理解递归和迭代的转换关系学习常见的树形DP问题研究平衡二叉树的维护AVL树红黑树我在刚开始学习二叉树时曾经花费两周时间专门练习各种遍历算法直到能够闭眼写出无bug的代码。这种基础训练在后来的面试和工程实践中带来了巨大的回报。