0129. Sum Root to Leaf Numbers¶
题目信息¶
- 题号:
求根节点到叶节点数字之和
- 难度:
Medium
- 主题:
二叉树、深度优先搜索、路径状态、十进制前缀
- 原题:
- 重点:
将完整路径压缩为十进制前缀,只在真正叶节点结算,并理解递归参数与显式栈元素的对应关系
题目重述¶
给定一棵二叉树,每个节点保存 0..9 的一个数字。每条从根节点到叶节点的路径,按访问顺序组成一个
十进制整数;返回所有这些整数之和。只有左右孩子都为空的节点才是叶节点,路径中的前导零按普通整数规则
处理。题目保证最终答案可用 32 位有符号整数表示。
自建示例¶
root = [3, 1, 7, 0, 4]:三条路径表示310、314、37,返回661;root = [0, null, 6, null, 2]:唯一数字是062,数值为62;root = [5, 2, null, 9]:节点2仍有左孩子,不是叶子;唯一完整路径为5 -> 2 -> 9, 返回529。
C++ 实现¶
#include <stack>
#include <utility>
#include <vector>
class Solution {
private:
void collectCompletePath(
TreeNode* node,
std::vector<int>& digits,
long long& total
) {
if (node == nullptr) {
return;
}
digits.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) {
long long number = 0;
for (int digit : digits) {
number = number * 10 + digit;
}
total += number;
} else {
collectCompletePath(node->left, digits, total);
collectCompletePath(node->right, digits, total);
}
digits.pop_back();
}
long long sumWithPrefix(TreeNode* node, long long parentPrefix) {
if (node == nullptr) {
return 0;
}
const long long current = parentPrefix * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) {
return current;
}
return sumWithPrefix(node->left, current) +
sumWithPrefix(node->right, current);
}
long long sumWithExplicitStack(TreeNode* root) {
if (root == nullptr) {
return 0;
}
std::stack<std::pair<TreeNode*, long long>> pending;
pending.push({root, 0});
long long total = 0;
while (!pending.empty()) {
auto [node, parentPrefix] = pending.top();
pending.pop();
const long long current = parentPrefix * 10 + node->val;
if (node->left == nullptr && node->right == nullptr) {
total += current;
continue;
}
if (node->right != nullptr) {
pending.push({node->right, current});
}
if (node->left != nullptr) {
pending.push({node->left, current});
}
}
return total;
}
public:
int sumNumbers(TreeNode* root) {
return static_cast<int>(sumWithPrefix(root, 0));
}
};
题解¶
原始做法:先保存路径,再在叶子解释它¶
从根到叶的选择空间天然是一棵树:到达节点后,下一步可能进入左孩子或右孩子。最直接的 DFS 用
digits 保存当前路径;进入节点时追加一位,退出时弹出一位。到达叶子后再从头扫描整个数组,按十进制
规则还原数字并加入总和。
collectCompletePath 的回溯状态是正确的:递归进入某节点时,digits 恰好包含根到该节点的路径;
返回父节点前弹出当前位,左右分支不会互相污染。可是多个叶子共享长前缀时,每个叶子都会再次遍历相同的
前缀。保存每一位也超过了后续计算真正需要的信息。
结构信息:追加一位只依赖已有数值¶
若父路径已经表示整数 prefix,在末尾追加当前数字 digit 的结果固定为:
current = prefix * 10 + digit
后续无论再追加哪一位,都只需要 current,不需要知道此前各位分别是什么。于是完整路径数组可以压缩为
一个十进制前缀:递归参数携带父节点之前的值,进入当前节点时更新一次,再把同一个 current 分别交给
左右子树。
这个状态也自然处理前导零。例如 0 -> 6 -> 2 依次得到 0、6、62,无需构造字符串、删除
零或单独解析。
叶节点是唯一结算点¶
路径必须从根结束于叶子。只有 left == nullptr && right == nullptr 同时成立,current 才代表一条
完整答案。只判断“至少一个孩子为空”会把单孩子树中的内部节点提前结算;例如 5 -> 2 -> 9 中节点
2 的右孩子为空,但 52 并不是合法根到叶数字。
空指针分支返回零,表示这侧没有叶子、对总和没有贡献。非叶节点的所有完整路径要么进入左子树,要么进入 右子树,两组叶子互不重叠,因此两次递归的返回值可直接相加。
具体走读¶
对 [3, 1, 7, 0, 4],递归状态按路径演进如下:
当前节点 |
父前缀 |
更新后 |
动作 |
|---|---|---|---|
|
|
|
非叶,传给两个孩子 |
|
|
|
非叶,继续进入 |
|
|
|
叶子,返回 |
|
|
|
叶子,返回 |
|
|
|
叶子,返回 |
节点 1 返回 310 + 314,根节点再加右侧 37。前缀 31 只计算一次并传给两个分支,没有在
两个叶子处重新扫描 3, 1。
递归与显式栈的状态对应¶
sumWithPrefix 的一次函数调用隐含保存 (node, parentPrefix)。sumWithExplicitStack 把这对状态
直接放进 pending,弹出后执行完全相同的前缀更新和叶子判断。先压右孩子再压左孩子只是让左侧先处理,
不影响加法结果;树中节点有唯一父路径,也不需要访问集合。
显式栈不是更优的渐进算法,而是在树很深、希望避免递归调用栈时的实现替代。主解选择递归前缀,因为状态 转移和子树返回值的含义最直接;路径数组法保留为演进起点,显式栈则展示递归帧究竟保存了什么。
正确性与复杂度¶
每个叶节点在树中只有一条根路径。DFS 恰好访问该叶子一次,并通过逐位递推得到这条路径的十进制值,所以
每个合法数字加入一次;内部节点从不结算,因此没有额外数字。每个节点只做常数工作,主解时间 O(n)、
递归空间 O(h),其中 h 为树高。显式栈最坏占 O(n);完整路径基线还会在每个叶子重新扫描路径,
最坏时间可达 O(nh)。代码使用 long long 保存中间前缀与部分和,再按题目保证转换为 int。