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

二叉树路径求和需递归回溯，不能仅用dfs遍历；必须维护从根到叶子的完整路径或实时计算路径数字和，关键在于回溯恢复状态，支持负数且注意整数溢出与十进制拼接逻辑。

c++如何实现二叉树的所有路径求和

二叉树路径求和需要递归回溯，不能只靠DFS遍历

直接用深度优先遍历（dfs）但不维护路径状态，会漏掉分支或重复累加。关键在于：每到一个叶子节点，必须拿到从根到它的完整路径值（比如 [1,2,5]），再求和；而中间节点要向下传递当前路径和，同时保证回退时能撤销影响——这就是回溯的必要性。

常见错误是只传一个累加变量 sum，这样无法区分不同路径，也无法还原上层状态。正确做法是传路径容器（如 vector<int></int>）或实时计算路径和并回退。

推荐用引用传参 + push_back()/pop_back() 实现回溯，避免拷贝开销
若只需求“所有路径的数字和”（如 1->2->5 算 125），注意整数溢出，建议用 long long
若路径数字拼接后过大（如深度 > 10），应改用字符串处理再转数，或直接按位计算

用 vector& path 记录路径，遇到叶子就 push 到结果

这是最直观、调试友好的方式。每次进入节点就把值加入 path，离开前弹出，确保 path 始终反映当前递归栈对应的路径。

void dfs(TreeNode* root, vector<int>& path, vector<vector>>& res) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right) {
        res.push_back(path); // 叶子：保存当前完整路径
    } else {
        dfs(root->left, path, res);
        dfs(root->right, path, res);
    }
    path.pop_back(); // 回溯：恢复上层状态
}</vector></int>

调用前初始化空 path 和 res，结束后对每个 res[i] 求和即可。注意：不要在递归中直接修改 res 里的子向量，push_back(path) 是深拷贝。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

如果只要路径和（非路径本身），可优化为单个 long long 参数

当题目只要求返回所有路径构成的数字之和（如 LeetCode 129），不必存整条路径，只需边走边算：cur_sum = cur_sum * 10 + root->val。这样空间 O(h)，比存路径 O(h²) 更优。

递归入口传 0 作为初始值
每层更新 cur_sum，叶子节点直接累加进全局 total
无需回溯，因为参数是值传递，自然“撤销”

示例关键逻辑：

void dfs(TreeNode* root, long long cur_sum, long long& total) {
    if (!root) return;
    cur_sum = cur_sum * 10 + root->val;
    if (!root->left && !root->right) {
        total += cur_sum;
        return;
    }
    dfs(root->left, cur_sum, total);
    dfs(root->right, cur_sum, total);
}