113. 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] ]

Subscribe to see which companies asked this question

其实有两种传结果的方法，我写的是传引用的方式。 代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // static int total; class Solution { public: void dfs(TreeNode* root,const int sum,int tempSum,vector<int>& temp,vector<vector<int>>& ans) { if(root->left==NULL && root->right==NULL) { // cout<<tempSum<<endl; if(tempSum==sum) { ans.push_back(vector<int>(temp.begin(),temp.end())); } return ; } else { if(root->left) { temp.push_back(root->left->val); dfs(root->left,sum,tempSum+root->left->val,temp,ans); temp.pop_back(); } if(root->right) { temp.push_back(root->right->val); dfs(root->right,sum,tempSum+root->right->val,temp,ans); temp.pop_back(); } } return ; } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> ans; if(root==NULL) return ans; vector<int> temp; temp.push_back(root->val); dfs(root,sum,root->val,temp,ans); return ans; } };