Path
Sum II:
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
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] ]
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { // Start typing your C/C++ solution below // DO NOT write int main() function if ( !root ) return vector<vector<int> >(); vector<vector<int> > ans; vector<int> path; solve(root,sum,ans,path); return ans; } void solve(TreeNode* root,int sum,vector<vector<int> >& ans,vector<int>& path) { if ( !root ) return; path.push_back(root->val); sum-=root->val; if ( !root->left && !root->right ) { if (sum==0) ans.push_back(path); } else { solve(root->left,sum,ans,path); solve(root->right,sum,ans,path); } path.pop_back(); } };