1. 二叉树算法实战从平衡性检测到路径遍历今天继续代码随想录算法训练营的第15天打卡我们集中攻克了四个经典的二叉树问题平衡二叉树判断110题、所有路径遍历257题、左叶子节点求和404题以及完全二叉树节点计数222题。这几个问题覆盖了二叉树算法中的多个核心考点特别适合用来检验递归和迭代两种思维方式的掌握程度。在实际面试中二叉树类问题出现的频率极高。根据我的刷题经验像平衡二叉树判断这类基础问题经常作为热身题出现而路径遍历和节点计数则更考验对递归终止条件的把控能力。下面我就结合具体代码实现详细拆解每个问题的解决思路和优化技巧。2. 平衡二叉树判断110题2.1 问题定义与递归思路平衡二叉树的定义是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。判断一棵树是否平衡最直观的方法就是递归地检查每个节点的左右子树高度差。def isBalanced(root): def height(node): if not node: return 0 return max(height(node.left), height(node.right)) 1 if not root: return True left_height height(root.left) right_height height(root.right) return abs(left_height - right_height) 1 and isBalanced(root.left) and isBalanced(root.right)这个解法虽然直观但存在明显的效率问题——对于每个节点都要递归计算其子树高度导致时间复杂度达到O(n^2)。在实际面试中面试官通常会要求优化这个解法。2.2 优化解法自底向上计算更高效的解法是在计算高度的同时判断平衡性一旦发现不平衡就直接返回。这样每个节点只需要访问一次时间复杂度降为O(n)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作为标记这样上层节点可以立即知道整棵树不平衡无需继续计算。3. 二叉树的所有路径257题3.1 深度优先遍历实现这个问题要求返回从根节点到所有叶子节点的路径。典型的DFS应用场景需要注意路径的构建方式def binaryTreePaths(root): 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) paths [] dfs(root, ) return paths这个解法在字符串拼接上有些低效因为每次递归调用都会创建新的字符串。对于大型二叉树这会带来不必要的内存开销。3.2 优化方案使用列表回溯更高效的做法是使用列表来构建路径在递归返回时回溯def binaryTreePaths(root): def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: paths.append(-.join(path)) dfs(node.left, path) dfs(node.right, path) path.pop() paths [] dfs(root, []) return paths这种实现方式的时间复杂度是O(n)空间复杂度在最坏情况下树退化为链表也是O(n)。4. 左叶子之和404题4.1 左叶子的识别条件这个问题要求计算所有左叶子节点的和。关键点在于准确识别什么是左叶子节点必须是某个节点的左子节点必须是没有子节点的叶子节点def sumOfLeftLeaves(root): if not root: return 0 def isLeaf(node): return not node.left and not node.right total 0 if root.left and isLeaf(root.left): total root.left.val total sumOfLeftLeaves(root.left) total sumOfLeftLeaves(root.right) return total4.2 迭代解法示例虽然递归解法简洁但面试时可能被要求用迭代实现。使用栈的DFS迭代版本def sumOfLeftLeaves(root): if not root: return 0 stack [(root, False)] total 0 while stack: node, is_left stack.pop() if not node.left and not node.right and is_left: total node.val if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, True)) return total这个解法通过元组的第二个元素标记节点是否是左子节点逻辑清晰且易于理解。5. 完全二叉树的节点个数222题5.1 完全二叉树的性质利用完全二叉树的特点是除了最后一层其他层都完全填满且最后一层的节点都靠左排列。利用这个性质可以优化普通的节点计数方法def countNodes(root): if not root: return 0 left_height 0 node root while node: left_height 1 node node.left right_height 0 node root while node: right_height 1 node node.right if left_height right_height: return 2**left_height - 1 return 1 countNodes(root.left) countNodes(root.right)这个解法的时间复杂度是O(logN * logN)因为每次递归调用都只需要计算左右子树的高度。5.2 二分查找优化更进一步的优化是利用二分查找确定最后一层的节点数def countNodes(root): if not root: return 0 def exists(idx, depth, node): left, right 0, 2**depth - 1 for _ in range(depth): mid (left right) // 2 if idx mid: node node.left right mid else: node node.right left mid 1 return node is not None depth 0 node root while node.left: depth 1 node node.left left, right 1, 2**depth while left right: mid (left right) // 2 if exists(mid - 1, depth, root): left mid 1 else: right mid - 1 return 2**depth - 1 left - 1虽然这个解法的时间复杂度也是O(logN * logN)但实现起来更复杂适合在特别关注性能的场景下使用。6. 常见问题与调试技巧6.1 递归栈溢出处理当处理深度很大的二叉树时递归解法可能会导致栈溢出。解决方法包括改用迭代实现使用尾递归优化如果语言支持增加递归深度限制临时解决方案6.2 边界条件检查二叉树问题常见的边界条件包括空树处理只有根节点的树左/右子树为空的情况退化为链表的树6.3 调试打印技巧在递归函数中添加打印语句可以帮助理解调用过程def dfs(node, path, depth0): print( *depth fVisiting {node.val if node else None}) # 其余代码...7. 算法选择与性能考量对于不同的二叉树问题选择合适的方法至关重要问题类型推荐方法时间复杂度空间复杂度平衡判断自底向上递归O(n)O(h)路径遍历DFS回溯O(n)O(h)左叶子求和带标记的DFSO(n)O(h)节点计数完全二叉树优化O(logN^2)O(logN)在实际编码时建议先写出最直观的解法然后根据问题特点逐步优化。理解每个优化步骤背后的原因比记住解法更重要。