C++如何实现二叉树从根到叶子的所有路径求和-C++-PHP中文网

递归遍历+路径累加求和的核心是下行时实时更新数值和，叶子节点（左右子树均空）才收集结果；推荐传值避免回溯错误，空根直接返回0，单节点视为叶子参与求和。

c++如何实现二叉树从根到叶子的所有路径求和

用递归遍历 + 路径累加求和

核心思路是边递归下行边维护当前路径和，到底层叶子节点时把和加入结果集。关键不是存路径字符串，而是实时更新数值——避免字符串拼接开销和内存浪费。

sumNumbers 这类题（LeetCode 129）要求根到叶形成的数字之和，比如 1→2→3 算作 123，此时需用 curr = curr * 10 + node->val
若题目只要路径上节点值的算术和（如 1+2+3=6），直接传入累加值即可，无需乘法
必须判断叶子节点：仅当 node->left == nullptr && node->right == nullptr 才收集结果，否则会多算中间节点

避免重复计算与错误回溯

递归中传参方式决定是否需要手动回溯。传值（pass-by-value）最安全；传引用（pass-by-reference）必须在返回前减去当前值，否则上层路径和会被污染。

推荐写法：dfs(node->left, curr + node->val) —— 每次调用新建局部值，天然无副作用
错误写法：curr += node->val; dfs(node->left, curr); curr -= node->val; 容易漏掉某一分支的回溯
如果用 vector 存路径再求和，空间复杂度升为 O(h²)（每层拷贝），而纯数值传递保持 O(h)

处理空树与单节点边界情况

空根节点（root == nullptr）应返回 0 或空结果，取决于题目定义；单节点树要确保它被识别为叶子并参与求和。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

入口处必须判空：if (!root) return 0;，否则递归进 nullptr 会导致崩溃或未定义行为
单节点时，root->left 和 root->right 均为 nullptr，满足叶子条件，root->val 会被计入
不要用 !node 替代 node == nullptr，尤其在自定义智能指针场景下可能隐式转换出错

C++ 实现示例（算术和版本）

以下是最简可用代码，适配 LeetCode 257 类路径和需求（非数字拼接）：

int sumRootToLeaf(TreeNode* root) {
    if (!root) return 0;
    int total = 0;
    dfs(root, 0, total);
    return total;
}
<p>void dfs(TreeNode* node, int curr, int& total) {
if (!node) return;
curr += node->val;
if (!node->left && !node->right) {
total += curr;
return;
}
dfs(node->left, curr, total);
dfs(node->right, curr, total);
}</p>

注意 total 用引用传入是为避免全局变量；若改用返回值方式，需处理左右子树各自的和，逻辑略冗余。实际调试时，建议在叶子处加 cout 快速验证路径值是否符合预期。

真正容易被忽略的是：所有路径和必须严格从根出发、终止于叶子，中途任何 return 都不能跳过叶子判定，哪怕节点值为 0 也不能提前剪枝。