aboutsummaryrefslogtreecommitdiff
path: root/path_sum2.cpp
blob: 3e64ee3ad17ddbfac642175d38112f10ba26542e (plain)
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
#include "leetcode.h"

class Solution {
public:
  vvd(int) pathSum(TreeNode *root, int targetSum) {
    vvd(int) ans;
    vector<int> d;
    dfs(root, targetSum, d, ans);
    return ans;
  }

private:
  void dfs(TreeNode *root, int targetSum, vector<int> d, vvd(int) & ans) {
    if (root == NULL)
      return;
    d.push_back(root->val);
    targetSum -= root->val;
    if (targetSum == 0 && root->left == NULL && root->right == NULL) {
      ans.push_back(d);
      return;
    }
    dfs(root->left, targetSum, d, ans);
    dfs(root->right, targetSum, d, ans);
  }
};