(每日一道算法题)求根节点到叶节点数字之和

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

 

理解问题：我们需要计算二叉树中从根节点到每个叶节点的路径所表示数字的总和。路径表示的数字由路径上的节点值按顺序组成。

问题分析

二叉树的每个节点存放着0-9的数字，从根节点到叶节点的路径构成了一个数字。例如，路径1->2->3表示数字123。我们需要计算所有这样的路径数字之和。

关键点：

• ​​叶节点​​：没有子节点的节点（即路径终点）
• ​​数字生成规则​​：当前路径数字 = 上一层路径数字×10 + 当前节点值
• ​​总和计算​​：对所有叶节点的路径数字求和

解决方案：深度优先搜索（DFS）

采用递归方法遍历每条路径，在遍历过程中累积路径数字，到达叶节点时将当前路径数字加入总和。

class Solution {public int sumNumbers(TreeNode root) {// 从根节点开始遍历，初始路径值为0return dfs(root, 0);}private int dfs(TreeNode node, int currentSum) {if (node == null) return 0;// 更新当前路径值：原值×10 + 当前节点值currentSum = currentSum * 10 + node.val;// 如果是叶节点，返回当前路径值if (node.left == null && node.right == null) {return currentSum;}// 递归计算左右子树的结果，并返回它们的和int leftSum = dfs(node.left, currentSum);int rightSum = dfs(node.right, currentSum);return leftSum + rightSum;}
}

算法流程

​​开始遍历​​：从根节点开始，初始路径值为0

​​更新路径值​​：路径值 = 路径值×10 + 当前节点值

​​叶节点判断​​：

• 如果是叶节点，返回当前路径值
• 否则递归遍历子节点

​​结果合并​​：返回左右子树结果之和

 

复杂度分析

• ​​时间复杂度​​：O(N) - 每个节点只访问一次
• ​​空间复杂度​​：O(H) - 递归调用栈深度（H为树的高度）

优化与注意事项

1. ​​空节点处理​​：递归前检查子节点是否存在
2. ​​大数问题​​：题目限定节点值为0-9，路径深度有限，无需担心溢出
3. ​​迭代替代方案​​：可使用DFS栈或BFS队列实现，但递归更直观