二叉树算法实战：修剪、构建与累加树解析

1. 二叉树算法复健概述今天是我算法复健训练的第17天重点攻克力扣(LeetCode)上与二叉树相关的三道经典题目669、108和538。作为数据结构中最基础也最重要的非线性结构之一二叉树在算法面试中的出现频率高达65%以上根据2023年LeetCode官方统计。这三道题分别代表了修剪二叉搜索树、有序数组转BST和BST累加树这三种典型应用场景。我在实际面试和刷题过程中发现很多同学对二叉树的理解停留在表面遇到变种题目就容易卡壳。这次复健我特意选择了这三道具有代表性的题目通过对比练习来深入掌握二叉树的操作技巧。下面我会逐题拆解解题思路并分享一些教科书上不会讲的调试技巧。2. LC 669. 修剪二叉搜索树2.1 题目核心要求给定一个二叉搜索树(BST)和边界[L, R]需要修剪树使得所有节点的值都在这个范围内。要求保持BST的性质并且要正确处理子树可能需要完全删除的情况。关键点不能简单地删除不符合范围的节点因为其子树中可能存在有效节点。这是很多初学者容易犯错的地方。2.2 递归解法实现def trimBST(root, L, R): if not root: return None if root.val L: return trimBST(root.right, L, R) if root.val R: return trimBST(root.left, L, R) root.left trimBST(root.left, L, R) root.right trimBST(root.right, L, R) return root这个解法的时间复杂度是O(N)空间复杂度最坏情况O(H)H为树高。我通过画图分析了几种边界情况根节点小于L整个左子树都不符合要求根节点大于R整个右子树都不符合要求节点在范围内需要递归处理左右子树2.3 迭代解法优化递归解法虽然直观但在处理超大树时可能栈溢出。下面是迭代版本def trimBST(root, L, R): # 先找到新的根节点 while root and (root.val L or root.val R): root root.right if root.val L else root.left # 修剪左子树 curr root while curr: while curr.left and curr.left.val L: curr.left curr.left.right curr curr.left # 修剪右子树 curr root while curr: while curr.right and curr.right.val R: curr.right curr.right.left curr curr.right return root3. LC 108. 将有序数组转换为二叉搜索树3.1 题目分析要求将一个升序排列的数组转换为高度平衡的BST。这里的关键是理解高度平衡的定义——每个节点的左右子树高度差不超过1。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(mid1, right) return root return helper(0, len(nums)-1)这个解法的时间复杂度是O(N)空间复杂度O(logN)递归栈。我总结了几个优化点对于大数组使用迭代代替递归可以随机选择中间偏左或偏右的节点来增加树的多样性实际测试发现Python中切片操作会显著增加内存使用所以使用索引区间而非切片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 mid1 right: node.right TreeNode(0) stack.append((mid1, right, node.right)) return root4. LC 538. 把二叉搜索树转换为累加树4.1 题目理解这道题要求我们将BST转换为累加树使得每个节点的值变成原树中大于或等于该节点值的和。这实际上是要求我们按照降序遍历BST并累加。4.2 递归解法def convertBST(root): total 0 def helper(node): nonlocal total if not node: return helper(node.right) total node.val node.val total helper(node.left) helper(root) return root这个解法的时间复杂度O(N)空间复杂度O(H)。我发现在实际编码时有几个易错点必须先遍历右子树再处理当前节点需要使用nonlocal或类变量来维护累加状态空节点处理容易遗漏4.3 Morris遍历优化为了优化空间复杂度可以使用Morris遍历def convertBST(root): total 0 curr root while curr: if not curr.right: total curr.val curr.val total curr curr.left else: succ curr.right while succ.left and succ.left ! curr: succ succ.left if not succ.left: succ.left curr curr curr.right else: succ.left None total curr.val curr.val total curr curr.left return root5. 二叉树算法通用技巧5.1 调试与验证方法在二叉树问题调试时我总结了一套可视化方法实现树的层次遍历打印使用Graphviz生成树形图对递归解法打印递归深度和当前节点值def printTree(root): if not root: print(Empty tree) return from collections import deque q deque([root]) while q: level_size len(q) for _ in range(level_size): node q.popleft() print(node.val, end ) if node.left: q.append(node.left) if node.right: q.append(node.right) print()5.2 常见错误分析空指针异常忘记检查节点是否为null递归终止条件错误导致无限递归修改了树结构但忘记更新指针特别是在删除节点时混淆了值传递和引用传递Python中是引用传递但要小心可变对象5.3 性能优化建议对于大型树优先考虑迭代解法使用记忆化技术避免重复计算合理利用BST的性质减少不必要的遍历在实际面试中先给出暴力解法再优化6. 二叉树问题分类总结6.1 遍历类问题前序、中序、后序递归/迭代实现层次遍历及其变种Morris遍历及其应用场景6.2 构造类问题根据遍历序列重建二叉树平衡BST的构建特殊二叉树的生成6.3 修改类问题节点删除与树修剪属性修改如本题的累加树结构调整如旋转、翻转6.4 查询类问题属性查询深度、宽度等祖先关系查询路径和查询经过这天的集中训练我对二叉树的各种操作有了更深入的理解。特别是通过对比不同解法的实现让我对递归和迭代的转换更加熟练。在实际编码时建议先用小例子手动模拟算法流程这样可以避免很多低级错误。