CCI4.9.java

/*
    4.9 You are given a binary tree in which each node contains a value. 
    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.
 */

package chapter4;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author renli
 */
public class problem9 {
    
    public static void main(String[] args) {
        int[] a = {20, 8, 22, 4, 12, 10, 14};
        MyTree t = new MyTree();
        for (int i : a) t.put(i);
        List<List<Integer>> paths = getPaths(t.root, 22);
        for (List<Integer> l : paths) {
            for (int i : l) System.out.print(i + " ");
            System.out.print("\n");
        }
    }
    
    public static List<List<Integer>> getPaths(MyNode root, int value) {
        List<List<Integer>> result = new ArrayList<>();
        if (root.val == value) {
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            result.add(list);
        }
        MyNode sumRoot = createSumTree(root, 0);  
        searchPath(sumRoot, result, value);
        return result;
    }
 
    
    private static void searchPath(MyNode sumRoot, List<List<Integer>> allpath, int value) {
        searchSublist(sumRoot, value, sumRoot, allpath, new ArrayList<Integer>());
        if (sumRoot.left != null) searchPath(sumRoot.left, allpath, value);
        if (sumRoot.right != null) searchPath(sumRoot.right, allpath, value);
    }
    
    private static void searchSublist(MyNode sumNode, int value, MyNode source, List<List<Integer>> allpath, List<Integer> path) {
        if (sumNode == null) return;
        path.add(sumNode.val);      
        if (sumNode.val == value + source.val) {
            List<Integer> realpath = new ArrayList<>();
            for (int i = 1; i < path.size(); ++i) realpath.add(path.get(i) - path.get(i - 1));
            allpath.add(realpath);
        }
        if(sumNode.left != null) searchSublist(sumNode.left, value, source, allpath, new ArrayList<>(path));
        if(sumNode.right != null) searchSublist(sumNode.right, value, source, allpath, new ArrayList<>(path));
    }
    
    private static MyNode createSumTree(MyNode node, int sum) {
        if (node == null) return null;
        node.val += sum;
        if (node.left != null) node.left = createSumTree(node.left, node.val);
        if (node.right != null) node.right = createSumTree(node.right, node.val);
        return node;
    }
    
}