Path Sum II (Medium)

Description

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis

跟path sum I是一样的思路。记录一下路径就好了

My Solution

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
27
28
29
30
31
32
33
//C++
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int> >ans;
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<int> path;
        dfs(root,sum,path);
        return ans;
    }
    void dfs(TreeNode *root,int sum,vector<int> path){
        if(root==NULL)  return;
        if(root->left==NULL&&root->right==NULL){
            if(sum == root->val){
                path.push_back(root->val);
                ans.push_back(path);
            }
            return ;
        }
        path.push_back(root->val);
        dfs(root->left,sum-root->val,path);
        dfs(root->right,sum-root->val,path);
        path.pop_back();
    }
};