https://leetcode.cn/problems/path-sum-ii/

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2], targetSum = 0
输出：[]

一开始写了一坨返回值为vector<vector<int>>的递归函数，写了半天最后因为vector合并情况太多直接索性放弃了，后来才认识到这样的拷贝开销((

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    vector<vector<int>> res;
    vector<int> path; 
    void traversal(TreeNode* root, int targetSum) {
        if (!root->left && !root->right) {
            if (targetSum == root->val) {
               path.emplace_back(root->val);
               res.emplace_back(path);
               path.pop_back();
            }
            return;
        }
        path.emplace_back(root->val);
        if (root->left) traversal(root->left, targetSum - root->val);
        if (root->right) traversal(root->right, targetSum - root->val);
        path.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum){
        res.clear();
        if (!root) return res;
        traversal(root, targetSum);
        return res;
    }
};

也不是第一次见这样的私有变量用法，但还是感觉有点震撼。