# 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.
Note: A leaf is a node with no children.
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]
]
# Solution
Approach 1: DFS.
# Code (Python)
Approach 1:
class Solution:
def pathSum(self, root, target):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
result = []
path = [root]
self._find_sum(path, root.val, target, result)
return result
def _find_sum(self, path, sum_so_far, target, result):
node = path[-1]
if not node.left and not node.right and sum_so_far == target:
result.append(list(map(lambda node:node.val, path)))
return
if node.left:
path.append(node.left)
self._find_sum(path, sum_so_far + node.left.val, target, result)
path.pop()
if node.right:
path.append(node.right)
self._find_sum(path, sum_so_far + node.right.val, target, result)
path.pop()
# Code (C++)
Approach 1:
/**
* 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 {
private:
vector<vector<int>> paths;
void doPathSum(TreeNode* root, int sum, vector<int>& buf) {
if (root == NULL)
return;
buf.push_back(root->val);
if (!root->left && !root->right && sum == root->val)
paths.push_back(buf);
int newSum = sum - root->val;
if (root->left)
doPathSum(root->left, newSum, buf);
if (root->right)
doPathSum(root->right, newSum, buf);
buf.pop_back();
}
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<int> buf;
doPathSum(root, sum, buf);
return paths;
}
};