/
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
/
class Solution {
public:
void DFS(vector[HTML_REMOVED] path, TreeNode root, int sum, vector[HTML_REMOVED]> &result) {
if (!root) return;
sum -= root->val;
path.push_back(root->val);
if (!root->left && !root->right && sum == 0) {
result.push_back(path);
}
DFS(path, root->left, sum, result);
DFS(path, root->right, sum, result);
}
vector[HTML_REMOVED]> findPath(TreeNode* root, int sum) {
vector[HTML_REMOVED]> result;
if (!root) return result;
vector[HTML_REMOVED] path;
DFS(path, root, sum, result);
return result;
}
};