PathsWithSum (_4_12)

PathsWithSum.java

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

/**
 * Paths with Sum: You are given a binary tree in which each node contains
 * an integer value (which might be positive or negative).
 * Design an algorithm to count the number of paths that sum to a given value.
 * The path does not need to start or end at the root or a leaf,
 * but it must go downwards (traveling only from parent nodes to child nodes).
 * <p>
 * Hints: #6, #74, #52, #68, #77, #87, #94, #703, #708, #115
 */
public class PathsWithSum {
    public static void main(String[] args) {
        Node n10 = new Node(16, null, null);

        Node n9 = new Node(11, null, null);
        Node n8 = new Node(12, null, null);
        Node n7 = new Node(10, null, n10);

        Node n6 = new Node(8, null, null);
        Node n5 = new Node(9, null, null);

        Node n4 = new Node(6, n8, n9);
        Node n3 = new Node(5, n7, null);

        Node n2 = new Node(4, n5, n6);
        Node n1 = new Node(3, n3, n4);
        Node r = new Node(1, n1, n2);

        solution1(r, 8);
        solution1(r, 800);
        solution1(r, 26);
        solution1(r, 35);
        solution1(r, 34);
        solution1(r, 31);
        solution1(r, 18);
        System.out.println();

        solution2(r, 8);
        solution2(r, 800);
        solution2(r, 26);
        solution2(r, 35);
        solution2(r, 34);
        solution2(r, 31);
        solution2(r, 18);
    }

    private static void solution1(Node node, int i) {
        List<Integer> result = solution1(node, i, new ArrayList<>());
        System.out.println(result + " i: " + i);
    }

    private static List<Integer> solution1(Node n, int i, List<Integer> list) {
        System.out.print(".");
        if (n == null) {
            return null;
        }

        list.add(n.getValue());
        if (sum(list) >= i) {
            for (int j = 0; j < list.size(); j++) {
                List<Integer> collector = new ArrayList<>();
                if (sum(list, j, collector) == i) {
                    return collector;
                }
            }
        }

        List<Integer> result = solution1(n.getLeft(), i, list);
        return result == null ? solution1(n.getRight(), i, list): result;

    }

    public static void solution2(Node node, int i) {
        List<Integer> result = solution2(node, i, new ArrayList<>(), 0);
        System.out.println(result + " i: " + i);
    }

    private static List<Integer> solution2(Node n, int i, List<Integer> list, int lastSum) {
        System.out.print(".");
        if (n == null) {
            return null;
        }

        int value = n.getValue();
        list.add(value);
        lastSum += value;

        if (lastSum >= i) {
            List<Integer> collector = new ArrayList<>();

            for (int j = 0; j < list.size(); j++) {
                if (sum(list, j, collector) == i) {
                    return collector;
                }
                collector.clear();
            }
        }

        List<Integer> result = solution2(n.getLeft(), i, list, lastSum);
        return result == null ? solution2(n.getRight(), i, list, lastSum): result;
    }

    public static int sum(List<Integer> list) {
        int sum = 0;
        for (Integer i : list) {
            System.out.print(".");
            sum += i;
        }

        return sum;
    }

    public static int sum(List<Integer> list, int j, List<Integer> collector) {
        int sum = 0;
        for (int i = j; i < list.size(); i++) {
            System.out.print(".");
            collector.add(list.get(i));
            sum += list.get(i);
        }
        return sum;
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + " ";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        return value == node.value;
    }
}