C++如何实现二叉树从根节点开始到所有叶子节点的路径总和汇总-C++-PHP中文网

直接结论：用深度优先递归，边走边累加节点值，到底部叶子时把当前路径和存入结果容器；关键在于汇总每条根到叶路径各自的和，而非计算单一总和。

c++如何实现二叉树从根节点开始到所有叶子节点的路径总和汇总

如何用递归遍历收集所有根到叶路径的和

直接结论：用深度优先递归，边走边累加节点值，到底部叶子时把当前路径和存入结果容器。关键不是“算总和”，而是“汇总每条路径各自的和”——很多人误以为要返回一个单一数字，实际需求是得到所有路径和组成的集合。

常见错误现象：sum 参数传值而非引用导致路径和丢失；没判断叶子节点（仅靠 left == nullptr && right == nullptr），漏掉单子树但无子节点的真叶子；递归回退时没手动回删当前节点值，造成路径污染。

必须用引用传递路径和变量（如 int& curr_sum）或用参数携带当前值（推荐后者，更安全）
叶子判定不能只看是否为空指针，要显式检查左右孩子都为空
递归调用前加当前节点值，调用后不需“减回去”——因为用的是值传递的当前和，天然隔离

void dfs(TreeNode* root, int curr_sum, vector<int>& res) {
    if (!root) return;
    curr_sum += root->val;
    if (!root->left && !root->right) {
        res.push_back(curr_sum);
        return;
    }
    dfs(root->left, curr_sum, res);
    dfs(root->right, curr_sum, res);
}</int>

为什么不用全局变量或静态变量存路径和

因为多线程或重复调用场景下会残留旧状态，且违反函数纯度原则。尤其当同一棵树被多次查询不同条件（比如带限制的路径和）时，全局 curr_sum 会干扰后续调用。

使用场景：LeetCode 112（是否存在某路径和）、113（返回所有路径）、437（路径和等于目标值的路径数）——它们底层都依赖同一套遍历逻辑，只是终止条件和收集方式不同。

传参方式让每次调用完全独立，curr_sum 在栈帧里自然生命周期管理
若需返回路径本身（而不仅是和），则要额外传 vector<int>&</int> 记录节点值，此时需在进入/退出时 push/pop ——但本题只需和，没必要存整条路径
性能上无差异，现代编译器对这种小整数传参优化极好

迭代写法怎么避免手动模拟栈混乱

迭代本质是手动维护 DFS 栈，难点在于每个栈元素必须同时携带节点指针和截至该节点的路径和。只存节点会导致无法还原当前和。

C++ Code Review Master

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

下载

错误做法：用两个独立栈分别存 TreeNode* 和 int，容易错位；或只存节点，另用 map 做节点到和的映射——增加哈希开销且易内存泄漏。

正确方式：定义结构体或 pair，例如 stack<pair int>></pair>，入栈时立即计算 curr_sum + node->val
出栈后直接用 pair 的 second 值判断是否叶子、是否存结果，逻辑清晰
迭代版本适合栈空间受限环境（防止递归爆栈），但代码行数多、可读性略低，日常开发优先递归

stack<pair int>> stk;
stk.push({root, root->val});
while (!stk.empty()) {
    auto [node, s] = stk.top(); stk.pop();
    if (!node->left && !node->right) res.push_back(s);
    if (node->right) stk.push({node->right, s + node->right->val});
    if (node->left)  stk.push({node->left,  s + node->left->val});
}</pair>