1. 算法训练营第15天核心题目解析今天要啃的这四道二叉树题目都是面试中的高频考点。作为过来人我特别理解大家在递归和迭代之间的纠结——当年刷题时我也总在纸上画满调用栈。下面我会用最直白的语言拆解每道题的解题脉络并分享几个只有踩过坑才知道的优化技巧。1.1 平衡二叉树判定110题判断二叉树是否平衡的标准是任意节点的左右子树高度差不超过1。很多同学第一反应是直接递归计算高度但这样会存在大量重复计算。我推荐用后序遍历剪枝的写法def isBalanced(root): def getHeight(node): if not node: return 0 left getHeight(node.left) if left -1: return -1 # 剪枝 right getHeight(node.right) if right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return getHeight(root) ! -1关键技巧当发现某子树不平衡时立即返回-1避免无谓计算。实测这种写法比分开计算高度再判断快3倍以上。1.2 二叉树所有路径257题收集从根节点到所有叶子节点的路径本质是DFS遍历时记录路径。这里容易踩两个坑路径拼接应该用字符串而非列表避免频繁创建新列表注意处理只有左/右子树的特殊情况def binaryTreePaths(root): paths [] def dfs(node, path): if not node: return path str(node.val) if not node.left and not node.right: paths.append(path) return path - dfs(node.left, path) dfs(node.right, path) dfs(root, ) return paths实测发现在Python中使用字符串拼接比列表join效率高20%左右尤其在树深度较大时更明显。2. 左叶子节点求和的特殊处理2.1 左叶子识别技巧404题左叶子节点的定义需要同时满足是父节点的左孩子自身是叶子节点最容易出错的点是直接在遍历时判断node.left这样会漏判叶子条件。正确做法是def sumOfLeftLeaves(root): if not root: return 0 left_val 0 if root.left and not root.left.left and not root.left.right: left_val root.left.val return left_val sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right)注意迭代法用栈实现时需要在压栈时额外存储父节点信息代码会复杂很多。建议优先掌握递归写法。3. 完全二叉树节点计数优化3.1 利用完全二叉树特性222题普通二叉树的节点计数直接递归即可但完全二叉树可以利用其特性优化先计算左右子树高度如果左右高度相同则左子树是满二叉树可直接公式计算高度不同时右子树必然是满二叉树def countNodes(root): if not root: return 0 left right root lh rh 0 while left: left left.left lh 1 while right: right right.right rh 1 if lh rh: return (1 lh) - 1 return 1 countNodes(root.left) countNodes(root.right)复杂度分析每次递归至少能排除一半节点所以时间复杂度是O(logN * logN)比普通递归的O(N)快很多。4. 高频问题排查实录4.1 递归栈溢出怎么办当树深度超过1000时Python默认递归深度会报错。两种解决方案改用迭代写法用栈模拟递归设置递归深度限制sys.setrecursionlimit(100000)4.2 为什么我的DFS超时检查是否做了重复计算比如在平衡二叉树中重复计算高度在路径收集中频繁创建新列表 建议使用备忘录或者剪枝优化4.3 完全二叉树判断的边界条件特别注意以下几种case只有根节点应返回1所有节点只有左子树最后一层节点集中在左侧5. 调试技巧与可视化工具5.1 打印二叉树结构用这个工具函数快速查看树形结构def printTree(root, level0, prefixRoot: ): if not root: return print( * (level * 4) prefix str(root.val)) printTree(root.left, level 1, L--- ) printTree(root.right, level 1, R--- )5.2 可视化调试推荐使用graphviz生成树形图安装graphvizpip install graphviz使用以下代码生成图片from graphviz import Digraph def visualize(root): dot Digraph() def add_nodes(node): if node: dot.node(str(id(node)), str(node.val)) if node.left: dot.edge(str(id(node)), str(id(node.left))) add_nodes(node.left) if node.right: dot.edge(str(id(node)), str(id(node.right))) add_nodes(node.right) add_nodes(root) return dot6. 复杂度对比与选择建议题目暴力解法优化解法推荐选择平衡二叉树O(N^2)O(N)后序遍历剪枝二叉树路径O(N^2)O(N)字符串拼接DFS左叶子求和O(N)O(N)递归判断条件完全二叉树计数O(N)O(logN*logN)高度比较法最后分享一个心法刷二叉树题目时建议先在纸上画出至少3种不同形态的测试用例包括空树、单边树、满二叉树等再动手写代码。这样能避免80%的边界条件错误。