Problem:
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,
|
1 2 3 4 5 6 7 |
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 |
return
|
1 2 3 4 |
[ [5,4,11,2], [5,8,4,5] ] |
Idea:
Recursion
Solution:
C++
|
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 |
// Author: Huahua // Runtime: 9 ms class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> ans; vector<int> curr; pathSum(root, sum, curr, ans); return ans; } private: void pathSum(TreeNode* root, int sum, vector<int>& curr, vector<vector<int>>& ans) { if(root==nullptr) return; if(root->left==nullptr && root->right==nullptr) { if(root->val == sum) { ans.push_back(curr); ans.back().push_back(root->val); } return; } curr.push_back(root->val); int new_sum = sum - root->val; pathSum(root->left, new_sum, curr, ans); pathSum(root->right, new_sum, curr, ans); curr.pop_back(); } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment