题解 | #二叉树根节点到叶子节点和为指定值的路径#

C++ -DFS-

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sumtmp int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        // 保存返回值
        vector<vector<int>> res;

        // 临时数组
        vector<int> rettmp;

        // 递归
        dfs(res, rettmp, root, sum, 0);
        return res;
    }


    //对所有路径进行查找，直到结束
    void dfs(vector<vector<int>>&res, vector<int>&rettmp, TreeNode* ROOT, int sum, int tmp) {
        //如果节点为空，返回
        if (ROOT == nullptr) return ;

        //保存值
        int sumtmp = tmp + ROOT->val;
        rettmp.push_back(ROOT->val);

        //如果是叶子节点，判断是否满足要求
        if (ROOT->left == nullptr  && ROOT->right == nullptr ) {
            if (sumtmp == sum) {
                res.push_back(rettmp);//找到一个满足要求的路径
            }
            return ;//返回上一层
        }

        //如果是左子树
        if (ROOT->left) {
            dfs(res, rettmp, ROOT->left, sum, sumtmp);

            //如果左边遍历完了，那么需要回溯一个
            rettmp.pop_back();
        }

        //如果是右子树
        if (ROOT->right) {
            dfs(res, rettmp, ROOT->right, sum, sumtmp);
            //如果右边遍历完了，那么需要回溯一个
            rettmp.pop_back();
        }

    }

};