129. Sum Root to Leaf Numbers
129. Sum Root to Leaf Numbers
题目
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. 0 <= Node.val <= 9- The depth of the tree will not exceed
10.
题目大意
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。
解题思路
这一题是 第 257 题 的变形题，第 257 题要求输出每条从根节点到叶子节点的路径，这一题变成了把每一个从根节点到叶子节点的数字都串联起来，再累加每条路径，求出最后的总和。实际做题思路基本没变。
使用深度优先搜索（DFS）来遍历二叉树，计算从根到叶子节点路径生成的数字之和。函数 sumNumbers 是入口函数，调用 dfs 函数进行递归。在 dfs 函数中，通过参数 currentSum 记录当前路径上的数字之和。当到达叶子节点时，返回当前路径的数字之和。整个递归过程计算了所有从根到叶子节点路径生成的数字之和。
代码
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function (root) {
const dfs = (root, currentSum) => {
if (!root) return 0;
currentSum = currentSum * 10 + root.val;
if (!root.left && !root.right) return currentSum;
let left = dfs(root.left, currentSum);
let right = dfs(root.right, currentSum);
return left + right;
};
return dfs(root, 0);
};
相关题目
- [112. 路径总和](./0112.md)
- [124. 二叉树中的最大路径和](https://leetcode.com/problems/binary-tree-maximum-path-sum)
- [988. 从叶结点开始的最小字符串](https://leetcode.com/problems/smallest-string-starting-from-leaf)