解题思路

• 先序遍历二叉树，先将根节点添加到路径内；
• 如果当前已经到了叶子结点，并且该条路径的和等于目标值，则将该条路径添加到结果中；
• 如果当前还没有到叶子结点，则递归遍历当前节点的左子树和右子树；
• 如果当前到了叶子结点，但是该条路径的和不等于目标值，则将当前值从路径和中减掉，并且弹出该路径。

时间复杂度

• 时间复杂度为：;
• 空间复杂度为：。

代码

#include <vector>

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;

    void dfs(TreeNode* root, int num, int count)
    {
        if(root == NULL) return;

        tmp.push_back(root->val);
        count += root->val;

        if(root->left == NULL && root->right == NULL)
        {
            if(count == num)
            {
                res.push_back(tmp);
            }
        }
        else 
        {
            dfs(root->left, num, count);
            dfs(root->right, num, count);
        }
        count -= tmp[-1];
        tmp.pop_back();
    }
  
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        dfs(root, sum, 0);
        return res;
    }
};