Binary Tree Path Sum - Lintcode

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

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

Example

Given a binary tree, and target =5:

     1
    / \
   2   4
  / \
 2   3

Analysis

Backtracking technique is needed to traverse the "left" and "right" path. Recursion is required to traverse exhaustively.

Solution

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

    List<Integer> path = new ArrayList<Integer>();
    path.add(root.val);
    helper(root, target-root.val, path, result);
    return result;
}

public void helper(TreeNode root, int target, List<Integer> path, List<List<Integer>> result){
    if (root.left == null && root.right == null){
        if (target == 0){
            result.add(new ArrayList<Integer>(path));
        }
    }

    if (root.left != null){
        path.add(root.left.val);
        helper(root.left, target - root.left.val, path, result);
        path.remove(path.size() - 1);
    }

    if (root.right != null){
        path.add(root.right.val);
        helper(root.right, target - root.right.val, path, result);
        path.remove(path.size() - 1);
    }
}

Binary Tree Path SumII - Lintcode

Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.

Analysis

Similar to Binary Tree Path Sum, except the traversal can start from any node, not just the root node and start at any node not only at the leave node. So another iterator is required to start the path at any level of the tree. And the check for the leave node in the helper method should be removed.

Solution

List<List<Integer>> result = new ArrayList<List<Integer>>();

public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
    iterate(root, target);
    return result;
}

public void iterate(TreeNode root, int target) {
    List<Integer> path = new ArrayList<Integer>();
    if (root != null) {
        path.add(root.val);
        helper(root, path, target - root.val);
        iterate(root.left, target);
        iterate(root.right, target);
    }
}

public void helper(TreeNode node, List<Integer> path, int target) {
    if (node == null) {
        return;
    }

    if (target == 0) {
        result.add(new ArrayList<Integer>(path));
    }

    if (node.left != null) {
        path.add(node.left.val);
        helper(node.left, path, target - node.left.val);
        path.remove(path.size() - 1);
    }

    if (node.right != null) {
        path.add(node.right.val);
        helper(node.right, path, target - node.right.val);
        path.remove(path.size() - 1);
    }
}