求根节点到叶节点数字之和
难度:
标签:
题目描述
给你一个二叉树的根节点
root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径1->2代表数字12从根到叶子节点路径1->3代表数字13因此，数字总和 = 12 + 13 =25
示例 2：
输入：root = [4,9,0,5,1] 输出：1026 解释： 从根到叶子节点路径4->9->5代表数字 495 从根到叶子节点路径4->9->1代表数字 491 从根到叶子节点路径4->0代表数字 40 因此，数字总和 = 495 + 491 + 40 =1026
提示：
- 树中节点的数目在范围
[1, 1000]内 0 <= Node.val <= 9- 树的深度不超过
10
代码结果
运行时间: 44 ms, 内存: 15 MB
/*
* 思路：
* 使用Java Stream API实现树的遍历和数字求和。
* 通过递归生成每条从根到叶子的路径数字，然后使用Stream的mapToInt和sum方法进行求和。
*/
import java.util.stream.Stream;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int sumNumbers(TreeNode root) {
return sumNumbersHelper(root, 0).mapToInt(Integer::intValue).sum();
}
private Stream<Integer> sumNumbersHelper(TreeNode node, int currentSum) {
if (node == null) return Stream.empty();
currentSum = currentSum * 10 + node.val;
if (node.left == null && node.right == null) {
return Stream.of(currentSum);
}
return Stream.concat(sumNumbersHelper(node.left, currentSum),
sumNumbersHelper(node.right, currentSum));
}
}解释
方法:
这个题解采用了深度优先搜索（DFS）的思路来解决问题。具体来说，它定义了一个辅助函数 dfs，用于递归遍历二叉树的每个节点。在遍历过程中，它维护了一个字符串 k，用于记录从根节点到当前节点的路径所表示的数字。当遍历到叶子节点时，将 k 转换为整数并加到全局变量 s 上。最终，s 的值就是所有根到叶子节点路径代表的数字之和。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在深度优先搜索（DFS）中，为什么选择使用字符串来累积路径值，而不是使用整数累加？
▷🦆
题解中提到当根节点为空时返回0，这种情况是否真的需要特别处理，或者说空树的输入是否在题目的有效输入范围内？
▷🦆
为什么在遍历到叶子节点时，直接将字符串转换为整数并累加到全局变量s上，有没有更高效的方法处理这一转换？
▷🦆
在处理叶子节点时，如果同时存在左右子节点为空的情况，是否考虑了节点值为0的情况对最终结果的影响？
▷相关问题
路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
从叶结点开始的最小字符串
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
注：字符串中任何较短的前缀在 字典序上 都是 较小 的：
- 例如，在字典序上
"ab"比"aba"要小。叶结点是指没有子结点的结点。
节点的叶节点是没有子节点的节点。
示例 1：
输入：root = [0,1,2,3,4,3,4] 输出："dba"
示例 2：
输入：root = [25,1,3,1,3,0,2] 输出："adz"
示例 3：
输入：root = [2,2,1,null,1,0,null,0] 输出："abc"
提示：
- 给定树的结点数在
[1, 8500]范围内 0 <= Node.val <= 25