Question4_9.java

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * You are given a binary tree in which each node contains an integer value (which might be positive or negative).
 * Design an algorithm to print 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.
 * 
 * Time  Complexity: O(n * h)
 * Space Complexity: O(h)
 */

public class Question4_9 {
    public LinkedList<ArrayList<Integer>> paths(TreeNode root, int target) {
        LinkedList<ArrayList<Integer>> allPaths = new LinkedList<ArrayList<Integer>>();
        recPaths(root, target, 0, new ArrayList<Integer>(), allPaths);
        return allPaths;
    }
    
    
    private void recPaths(TreeNode node, int target, int level, ArrayList<Integer> currPath, LinkedList<ArrayList<Integer>> allPaths) {
        if (node == null) {
            return;
        }
        
        if (level < currPath.size()) {
            currPath.set(level, node.value);
        } else {
            currPath.add(node.value);
        }
        int sum = 0;
        for (int i = level; i >= 0; --i) {
            sum += currPath.get(i);
            if (sum == target) {
                ArrayList<Integer> path = new ArrayList<Integer>();
                for (int j = i; j <= level; ++j) {
                    path.add(currPath.get(j));
                }
                allPaths.add(path);
            }
        }
        
        recPaths(node.left, target, level + 1, currPath, allPaths);
        recPaths(node.right, target, level + 1, currPath, allPaths);
    }
    
    
    public static void main(String[] args) {
        Question4_9 question4_9 = new Question4_9();
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.right.left = new TreeNode(-5);
        LinkedList<ArrayList<Integer>> paths = question4_9.paths(root, 1);
        for (ArrayList<Integer> path : paths) {
            for (Integer value : path) {
                System.out.print(value + "\t");
            }
            System.out.println();
        }
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}