Binary Tree Path Sum

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Have you met this question in a real interview? Yes Example Given a binary tree, and target = 5:

     1
    / \
   2   4
  / \
 2   3

return

[
  [1, 2, 2],
  [1, 4]
]

Solution: DFS and Divide conquer

public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
    if(root == null) {
        return new ArrayList<>();
    }
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> item = new ArrayList<Integer>();
    dfs(root, target, res, item);
    return res;
}

public void dfs(TreeNode root, int target, List<List<Integer>> res, List<Integer> item) {
    item.add(root.val);
    target -= root.val;
    if(root.left == null && root.right == null) {
        if(target == 0) {
            res.add(new ArrayList<>(item));
            return ;
        }
    }

    if(root.left != null) {
        dfs(root.left, target, res, item);
        item.remove(item.size() - 1);
    }
    if(root.right != null) {
        dfs(root.right, target, res, item);
        item.remove(item.size() - 1);
    }
}