113. Path Sum II (DFS) 20.3.18 Medium

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: -------------------------------------------------- DFS
------------------------------------------------------------ O(n) T, O(n) S
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res = []
        self.dfs(root, sum, [], res)
        return res   
    def dfs(self, root, sum, path, res):
        if not root:
            return
        if not root.left and not root.right and sum == root.val:
            res.append(path + [root.val])
        self.dfs(root.left, sum - root.val, path + [root.val], res)        # How to concatenate int to list !!!!
                                                                           # Use path instead of currlist.append() + currlist.pop()
        self.dfs(root.right, sum - root.val, path + [root.val], res)



Java Version:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, sum, new ArrayList<>(), res);
        return res;
    }
    
    public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            path.add(root.val);
            res.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
            return;
        }
        path.add(root.val);
        dfs(root.left, sum - root.val, path, res);
        dfs(root.right, sum - root.val, path, res);
        path.remove(path.size() - 1);
    }
}