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 number 123.

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（即节点数）。

---

思路二：回溯

1. 定义一个结果变量 sum 和一个路径变量 num。
2. 使用回溯算法，通过递归函数 backtrack 遍历组合的所有可能性。
3. 在 backtrack 函数中，当到达叶子节点时，将当前路径的数字 num 加入到结果变量 sum 中。
4. 在每一层递归中，将当前数字加入路径变量，然后递归调用下一层，最后去掉当前数字，回溯到上一层。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数，使用回溯方法遍历二叉树中的每一个节点，在每个节点处，进行常数级的操作。

• 空间复杂度：O(log n)，递归调用栈的深度取决于树的高度。在最好的情况下，二叉树是完全平衡的，树的高度为 O(log n)；最坏情况下，二叉树是链状的，树的高度为 n（即节点数）。

代码

DFS

/**
 * @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+