129. 求根节点到叶节点数字之和
129. 求根节点到叶节点数字之和
🟠 🔖 树
深度优先搜索
二叉树
🔗 力扣
LeetCode
题目
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:
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
- 使用深度优先搜索(DFS)来遍历二叉树,计算从根到叶子节点路径生成的数字之和。
- 函数
sumNumbers
是入口函数,调用dfs
函数进行递归。 - 在
dfs
函数中,通过参数currentSum
记录当前路径上的数字之和。 - 当到达叶子节点时,返回当前路径的数字之和。
- 整个递归过程计算了所有从根到叶子节点路径生成的数字之和。
复杂度分析
时间复杂度:
O(n)
,其中n
是二叉树的节点数,递归函数对每个节点访问一次。空间复杂度:
O(log n)
,递归调用栈的深度取决于树的高度。在最好的情况下,二叉树是完全平衡的,树的高度为O(log n)
;最坏情况下,二叉树是链状的,树的高度为n
(即节点数)。
思路二:回溯
- 定义一个结果变量
sum
和一个路径变量num
。 - 使用回溯算法,通过递归函数
backtrack
遍历组合的所有可能性。 - 在
backtrack
函数中,当到达叶子节点时,将当前路径的数字num
加入到结果变量sum
中。 - 在每一层递归中,将当前数字加入路径变量,然后递归调用下一层,最后去掉当前数字,回溯到上一层。
复杂度分析
时间复杂度:
O(n)
,其中n
是二叉树的节点数,使用回溯方法遍历二叉树中的每一个节点,在每个节点处,进行常数级的操作。空间复杂度:
O(log n)
,递归调用栈的深度取决于树的高度。在最好的情况下,二叉树是完全平衡的,树的高度为O(log n)
;最坏情况下,二叉树是链状的,树的高度为n
(即节点数)。
代码
/**
* @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);
};
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function (root) {
let sum = 0,
num = 0;
const backtrack = (root) => {
if (!root) return;
// 将当前数字加入路径变量
num = root.val + 10 * num;
// 到达叶子节点,将当前路径的数字 num 加入到结果变量 sum 中
if (!root.left && !root.right) {
sum += num;
num = (num - root.val) / 10;
return;
}
backtrack(root.left);
backtrack(root.right);
// 从路径变量中去掉当前数字
num = (num - root.val) / 10;
};
backtrack(root);
return sum;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
112 | 路径总和 | [✓] | 树 深度优先搜索 广度优先搜索 1+ | 🟢 | 🀄️ 🔗 |
124 | 二叉树中的最大路径和 | [✓] | 树 深度优先搜索 动态规划 1+ | 🔴 | 🀄️ 🔗 |
988 | 从叶结点开始的最小字符串 | 树 深度优先搜索 字符串 2+ | 🟠 | 🀄️ 🔗 |