[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] ]
[Analysis]
Know your DFS!
Don’t forget to pop!
If you do pop, make sure we are always pushing one element on each recursion!
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: vector<vector > res; vector r; void pathSumHelper(TreeNode *node, int target) { if (!node->left && !node->right && target == node->val) { // node is a leaf and it's a solution r.push_back(node->val); res.push_back(r); return; } // internal node, also makes sure that we always push a node r.push_back(node->val); int current = target - node->val; if (node->right) { pathSumHelper(node->right, current); r.pop_back(); } if (node->left) { pathSumHelper(node->left, current); r.pop_back(); } } public: vector<vector > pathSum(TreeNode *root, int sum) { res.clear(); r.clear(); if (!root) return res; pathSumHelper(root, sum); return res; } };