二叉树算法精讲：平衡判断、路径遍历与节点计数

1. 算法训练营第15天二叉树专题深度解析今天继续代码随想录算法训练营的打卡记录我们将集中攻克四个经典的二叉树问题平衡二叉树判断、所有路径遍历、左叶子节点求和以及完全二叉树节点计数。这几个问题看似基础但实际涵盖了二叉树遍历、递归技巧、边界条件处理等多个重要知识点是面试中的高频考点。我在刷题过程中发现很多初学者容易在这些问题上犯一些典型错误比如混淆平衡二叉树的定义、遗漏叶子节点的判断条件、错误计算完全二叉树的高度等。本文将结合我的实战经验详细拆解每个问题的解题思路并分享一些容易踩坑的细节。无论你是刚开始刷题的新手还是想巩固基础的进阶者相信这些内容都能给你带来实质性的帮助。2. 110.平衡二叉树深度优先的优雅解法2.1 问题理解与定义剖析平衡二叉树Balanced Binary Tree是指任意节点的左右子树高度差不超过1的二叉树。注意这里的高度是指从该节点到最远叶子节点的最长路径上的节点数。很多同学容易将高度和深度混淆这是第一个需要注意的关键点。在实际判断时我们需要递归地检查每个节点的左右子树高度差。如果发现任一节点的左右子树高度差大于1就可以立即判定这不是平衡二叉树。这种自底向上的递归检查方式时间复杂度为O(n)空间复杂度为O(h)其中h是树的高度。2.2 递归实现与优化技巧标准的递归解法会为每个节点计算左右子树高度然后比较差值。但直接实现会有重复计算的问题。更高效的做法是在计算高度的同时进行平衡性检查def isBalanced(root): def check(node): if not node: return 0 left check(node.left) right check(node.right) if left -1 or right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return check(root) ! -1关键技巧使用-1作为不平衡的标志这样可以在递归过程中提前终止不必要的计算。这种剪枝优化能将最坏情况下的时间复杂度从O(n^2)降到O(n)。2.3 常见错误与调试要点高度计算错误忘记空节点的高度为0导致叶子节点高度计算为1而不是正确的2提前返回问题没有正确处理递归的返回值导致部分子树未被检查边界条件遗漏忘记处理root为None的情况我在实际编码时发现使用可视化工具如Python的graphviz绘制二叉树结构能有效帮助验证高度计算的正确性。对于[3,9,20,null,null,15,7]这样的测试用例建议手动画出树形结构标出每个节点的高度这样能清晰看到递归过程。3. 257. 二叉树的所有路径回溯法的经典应用3.1 问题分析与解法选择这个问题要求我们找出从根节点到每个叶子节点的所有路径。这属于典型的深度优先搜索(DFS)应用场景需要配合回溯法来记录路径。与常规的DFS不同我们需要在访问到叶子节点时保存当前路径并在返回时正确移除已访问节点。选择前序遍历根-左-右是最自然的因为这样我们能按顺序构建路径字符串。递归和迭代两种实现方式各有优劣递归更简洁但可能有栈溢出风险迭代更可控但代码稍复杂。3.2 递归实现与字符串处理递归解法需要注意路径字符串的构建方式。直接使用字符串拼接在Python中效率较低更好的做法是使用列表记录节点值最后用-连接def binaryTreePaths(root): def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append(-.join(path)) dfs(node.left, path) dfs(node.right, path) path.pop() res [] dfs(root, []) return res性能提示在Python中字符串是不可变对象频繁拼接会产生大量临时对象。使用列表存储路径节点最后统一join能显著提升性能特别是在处理大型树时。3.3 迭代实现与栈的应用对于不喜欢递归或担心栈溢出的情况可以用显式栈实现迭代版本def binaryTreePaths(root): if not root: return [] res [] stack [(root, [str(root.val)])] while stack: node, path stack.pop() if not node.left and not node.right: res.append(-.join(path)) if node.right: stack.append((node.right, path [str(node.right.val)])) if node.left: stack.append((node.left, path [str(node.left.val)])) return res这种实现虽然代码量稍多但更符合某些面试官的偏好也避免了递归深度限制的问题。注意栈是后进先出所以要先压入右子树以保证左子树先被处理。4. 404. 左叶子之和识别真正的左叶子4.1 左叶子的精确定义这个问题最容易出错的地方在于对左叶子的理解。左叶子必须同时满足两个条件是父节点的左子节点自身是叶子节点没有左右子节点很多同学会错误地将所有左子节点都计入结果或者遗漏了根节点不可能成为左叶子这一边界条件。正确的判断应该通过父节点来进行当且仅当某个节点是叶子节点且是其父节点的左子节点时才计入总和。4.2 递归解法的实现细节递归解法需要从父节点的角度判断其左子节点是否为叶子def sumOfLeftLeaves(root): def helper(node, is_left): if not node: return 0 if not node.left and not node.right and is_left: return node.val return helper(node.left, True) helper(node.right, False) return helper(root, False)关键参数通过is_left标志位记录当前节点是否是父节点的左子节点。这种方法避免了直接判断父节点的复杂逻辑使代码更清晰。4.3 迭代解法与层序遍历虽然递归更简洁但迭代法也值得掌握。使用BFS时我们需要在将节点加入队列时记录它是否是左子节点from collections import deque def sumOfLeftLeaves(root): if not root: return 0 queue deque([(root, False)]) total 0 while queue: node, is_left queue.popleft() if not node.left and not node.right and is_left: total node.val if node.left: queue.append((node.left, True)) if node.right: queue.append((node.right, False)) return total这种写法在处理完全二叉树时特别高效因为可以提前终止不必要的遍历。注意这里使用了元组来同时存储节点和其左右属性这是处理树问题的常用技巧。5. 222. 完全二叉树的节点个数利用完全二叉树特性的高效解法5.1 完全二叉树的性质分析完全二叉树是指除了最后一层外其他层的节点都达到最大数量且最后一层的节点都集中在左侧。与普通二叉树不同完全二叉树的高度可以通过一直向左遍历来快速计算这个特性可以用于优化节点计数。最直观的解法是任何遍历前序、中序、后序或层序统计节点数时间复杂度O(n)。但对于完全二叉树我们可以利用其特性将时间复杂度优化到O(log n * log n)。5.2 高效算法的实现步骤算法思路计算左右子树的高度如果左右高度相同则左子树是满二叉树节点数为2^h - 1加上根节点共2^h个然后递归计算右子树如果高度不同则右子树是满二叉树高度少1递归计算左子树def countNodes(root): if not root: return 0 left_height get_height(root.left) right_height get_height(root.right) if left_height right_height: return (1 left_height) countNodes(root.right) else: return (1 right_height) countNodes(root.left) def get_height(node): height 0 while node: height 1 node node.left return height位运算技巧1 h 等价于2^h但效率更高。这是处理二叉树问题时常用的优化手段。5.3 复杂度分析与边界处理该算法的时间复杂度为O(log n * log n)因为每次递归调用都会减少问题规模至少一半每次计算高度需要O(log n)时间递归深度为O(log n)边界情况需要注意空树直接返回0单节点树只有根节点应返回1满二叉树的情况应该被正确处理在实际编码时建议添加打印语句输出每次递归的高度和计算结果这有助于验证算法的正确性。对于树[1,2,3,4,5,6]可以手动验证计算过程是否符合预期。6. 二叉树问题的通用解题框架通过这四个问题的练习我总结出二叉树问题的通用解题框架明确遍历顺序前序、中序、后序还是层序不同问题适合不同的遍历方式确定递归参数和返回值哪些信息需要从子问题传递到父问题处理边界条件空节点、单节点等特殊情况考虑优化空间能否利用二叉树特性如完全二叉树、BST性质进行优化验证测试用例至少验证空树、单节点树、完全倾斜树等边界情况对于面试准备建议将每个问题的递归和迭代解法都掌握并能够分析时间/空间复杂度。在实际编码时先理清思路再动手避免陷入细节而忽略整体逻辑。