# 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;
    }
};