Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        helper(root, new ArrayList<Integer>(), sum, result);
        return result;
    }

    public void helper(TreeNode root, List<Integer> path, int remain, List<List<Integer>> result) {
        if (root == null) return;
        path.add(root.val);
        if (root.left == null && root.right == null && root.val == remain) {
            result.add(new ArrayList<Integer>(path));//加进result的条件比较特殊,必须到了leaf且leaf的值等于remain
        }
        helper(root.left, path, remain - root.val, result);
        helper(root.right, path, remain - root.val, result);
        path.remove(path.size() - 1);
    }
}

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """

        if not root:
            return []

        ret = []
        self.helper(root, sum, [], ret)
        return ret

    def helper(self, root, sum, curr, ret):
        if not root:
            return
        if not root.left and not root.right and root.val == sum:
            ret.append(curr + [root.val])
            return
        self.helper(root.left, sum - root.val, curr + [root.val], ret)
        self.helper(root.right, sum - root.val, curr + [root.val], ret)