LeetCode 1022：二叉树路径二进制求和解析与实现

1. 问题背景与需求分析

今天我们来拆解LeetCode第1022题"从根到叶的二进制数之和"。这是一道典型的二叉树遍历问题，结合了二进制计算的特性。题目要求我们计算从根节点到每个叶子节点的路径所表示的二进制数的总和。

举个实际例子，假设我们有如下二叉树：

1 / \ 0 1 / \ / \ 0 1 0 1

那么从根到叶的路径有：

• 1→0→0 表示二进制100，即十进制4
• 1→0→1 表示二进制101，即十进制5
• 1→1→0 表示二进制110，即十进制6
• 1→1→1 表示二进制111，即十进制7 总和就是4+5+6+7=22

这道题的价值在于：

1. 考察对二叉树遍历的掌握程度
2. 训练二进制与十进制转换的思维
3. 培养路径累积计算的编程技巧
4. 是许多互联网公司面试的常见题型

2. 解题思路与算法选择

2.1 深度优先搜索(DFS)方案

DFS是最直观的解法，因为它天然适合处理路径累积问题。我们可以采用前序遍历的方式，在向下递归时传递当前路径的二进制值，到达叶子节点时将结果累加。

具体步骤：

1. 从根节点开始，初始路径值为0
2. 每向下访问一个节点，将当前值左移1位(相当于×2)并加上当前节点值
3. 如果是叶子节点，将当前值加入总和
4. 递归处理左右子树

时间复杂度：O(N)，需要访问每个节点一次 空间复杂度：O(H)，递归栈的深度等于树的高度

2.2 广度优先搜索(BFS)方案

BFS也可以解决这个问题，但需要额外存储每个节点对应的路径值。我们可以使用队列同时存储节点和对应的当前值。

实现步骤：

1. 初始化队列，放入根节点和值0
2. 从队列取出节点和当前值
3. 计算新值 = (当前值 << 1) | 节点值
4. 如果是叶子节点，累加到总和
5. 将非空子节点和新值放入队列
6. 重复直到队列为空

时间复杂度同样为O(N)，但空间复杂度在最坏情况下可能达到O(N)，因为要存储所有节点的信息。

3. 代码实现与细节解析

3.1 Python DFS实现

class Solution: def sumRootToLeaf(self, root: TreeNode) -> int: def dfs(node, current_sum): if not node: return 0 current_sum = (current_sum << 1) | node.val if not node.left and not node.right: return current_sum return dfs(node.left, current_sum) + dfs(node.right, current_sum) return dfs(root, 0)

关键点说明：

1. 使用嵌套函数dfs实现递归
2. current_sum << 1等价于乘以2
3. | node.val相当于加上当前节点值
4. 到达叶子节点时返回当前值，否则返回左右子树的和

3.2 Java BFS实现

class Solution { public int sumRootToLeaf(TreeNode root) { if(root == null) return 0; Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>(); queue.offer(new Pair<>(root, 0)); int sum = 0; while(!queue.isEmpty()) { Pair<TreeNode, Integer> pair = queue.poll(); TreeNode node = pair.getKey(); int current = pair.getValue(); current = (current << 1) | node.val; if(node.left == null && node.right == null) { sum += current; } if(node.left != null) { queue.offer(new Pair<>(node.left, current)); } if(node.right != null) { queue.offer(new Pair<>(node.right, current)); } } return sum; } }

注意事项：

1. 使用Pair同时存储节点和当前值
2. 每次从队列取出时更新当前值
3. 只有到达叶子节点时才累加
4. 需要处理空树的特殊情况

4. 边界条件与测试用例

4.1 常见边界情况

1. 空树：应该返回0
2. 单节点树：返回节点自身的值
3. 完全左斜树或右斜树
4. 所有节点值相同的情况
5. 大型树(测试递归深度)

4.2 推荐测试用例

# 测试用例1：示例中的树 # 1 # / \ # 0 1 # / \ / \ # 0 1 0 1 # 预期输出：22 # 测试用例2：单节点树 # 1 # 预期输出：1 # 测试用例3：全0树 # 0 # / \ # 0 0 # / \ / \ # 0 0 0 0 # 预期输出：0 # 测试用例4：左斜树 # 1 # / # 1 # / # 1 # 预期输出：7 (111二进制)

5. 算法优化与变种问题

5.1 空间优化技巧

对于DFS递归解法，虽然代码简洁，但在极端情况下(如树退化为链表)可能导致栈溢出。可以改用迭代式DFS：

def sumRootToLeaf(root): if not root: return 0 stack = [(root, 0)] total = 0 while stack: node, current = stack.pop() current = (current << 1) | node.val if not node.left and not node.right: total += current if node.right: stack.append((node.right, current)) if node.left: stack.append((node.left, current)) return total

5.2 相关问题扩展

1. 计算所有路径表示的十进制数的乘积
2. 找出二进制路径值最大的叶子节点
3. 计算路径值的平均值
4. 将问题扩展到n叉树的情况
5. 输出所有路径对应的二进制字符串

6. 面试技巧与常见错误

6.1 面试官可能问的问题

1. 为什么选择DFS而不是BFS？
2. 如何处理非常大的树(递归深度问题)？
3. 如果不允许使用位运算，如何实现？
4. 如何修改算法来记录所有路径？
5. 时间复杂度和空间复杂度分析？

6.2 常见错误与纠正

1. 忘记处理空树的情况
2. 在非叶子节点就进行累加
3. 位运算优先级错误(应该使用括号明确)
4. 递归终止条件写错
5. 在BFS实现中忘记同时存储节点和当前值

提示：在面试中，建议先明确问题要求，画出示例树，解释思路后再编码。注意边界的处理，写完代码后主动用测试用例验证。

7. 实际应用场景

虽然这个问题看起来是纯算法题，但其核心思想在实际中有广泛应用：

1. 文件系统路径的权限检查
2. 网络路由表的匹配算法
3. 决策树的路径概率计算
4. 游戏中的技能树解锁判断
5. 自动化测试中的UI操作路径记录

理解这种路径累积模式，可以帮助我们解决许多树形结构相关的实际问题。比如在微服务调用链分析中，我们可能需要统计各种调用路径的出现频率，其核心算法与本题非常相似。