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 -> 3
represents 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:
![](https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg)
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:
![](https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg)
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)