CareerCup

Simple solution using dfs(dfs())

public class Prob139 {
    public static class Res {
        private List<List<BinaryTreeNode<Integer>>> listOfPaths = new ArrayList<>();
        public Res() {

        }

        public void addList(List<BinaryTreeNode<Integer>> path) {
            listOfPaths.add(path);
        }

        public void printPaths() {
            for (List<BinaryTreeNode<Integer>> l: listOfPaths) {
                System.out.print("PATH: ");
                for (BinaryTreeNode<Integer> n: l) {
                    System.out.print(n.value + ", ");
                }
                System.out.println();
            }
        }
    }

    public static void simpleFindSumUpToK(BinaryTreeNode<Integer> node, int K) {
        if (node == null)
            return;

        Res res = new Res();
        List<BinaryTreeNode<Integer>> path = new ArrayList<>();
        dfs(node, K, 0, path, res);
        res.printPaths();

        simpleFindSumUpToK(node.left, K);
        simpleFindSumUpToK(node.right, K);
    }

    private static void dfs(BinaryTreeNode<Integer> node, int K, int sum, List<BinaryTreeNode<Integer>> path, Res res) {
        if (node == null)
            return;

        path.add(node);
        sum += node.value;

        if (sum == K) {
            res.addList(path);
            return;
        }

        List<BinaryTreeNode<Integer>> pathToLeft = new ArrayList<>(path);
        List<BinaryTreeNode<Integer>> pathToRight = new ArrayList<>(path);

        dfs(node.left, K, sum, pathToLeft, res);
        dfs(node.right, K, sum, pathToRight, res);
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1);
        root.left = new BinaryTreeNode<>(1);
        root.right = new BinaryTreeNode<>(2);
        root.left.right = new BinaryTreeNode<>(1);

        simpleFindSumUpToK(root, 3);
    }
}

Output:

PATH: 1, 1, 1, 
PATH: 1, 2,

I am thinking in a solution using sum arrays.
So, in linear time, I could create the arrays/subarrays containing the accumulative sum.
What do you think about this idea guys?
Thanks

package main

import (
	"fmt"
)

type TreeNode struct {
	value       int
	left, right *TreeNode
}

type PathWSum struct {
	path []*TreeNode
	sum  int
}

func allPath(root *TreeNode) []PathWSum {
	if root == nil {
		return []PathWSum{}
	}
	result := []PathWSum{{path: []*TreeNode{root}, sum: root.value}}
	tmp := append(allPath(root.left), allPath(root.right)...)
	for _, path := range tmp {
		newPath := PathWSum{path: append(path.path, root), sum: path.sum + root.value}
		result = append(result, newPath)
	}
	return result
}

func reversPath(path []*TreeNode) []*TreeNode {
	for i := 0; i < len(path)/2; i++ {
		path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
	}
	return path
}

func allPathFromRoot(root *TreeNode, sum int) [][]*TreeNode {
	result := [][]*TreeNode{}
	if root == nil {
		return result
	}
	if root.value == sum {
		result = append(result, []*TreeNode{root})
	}

	tmp := allPath(root.left)
	for _, path := range tmp {
		rPaths := allPath(root.right)
		for _, rPath := range rPaths {
			if path.sum+root.value+rPath.sum == sum {
				result = append(result, append(append(path.path, root), reversPath(rPath.path)...))
			}
		}
	}
	result = append(result, allPathFromRoot(root.left, sum)...)
	result = append(result, allPathFromRoot(root.right, sum)...)
	return result
}

func printPaths(paths [][]*TreeNode) {
	for _, path := range paths {
		for _, node := range path {
			fmt.Print(node.value)
			fmt.Print(" ")
		}
		fmt.Println()
	}
}

func main() {
	n31 := &TreeNode{value: 3}
	n32 := &TreeNode{value: 3}
	n1 := &TreeNode{value: 1}
	n_1 := &TreeNode{value: -1}
	n_2 := &TreeNode{value: -2}
	n6 := &TreeNode{value: 6}
	n4 := &TreeNode{value: 4}
	n5 := &TreeNode{value: 5}
	n2 := &TreeNode{value: 2}
	n_1.left = n31
	n_2.left = n32
	n4.left = n1
	n4.right = n_1
	n5.left = n_2
	n5.right = n6
	n2.left = n4
	n2.right = n5
	//             2
	//     4                 5
	//  1         -1       -2       6
	//           3        3

	printPaths(allPathFromRoot(n2, 13))
	// 1 4 2 5 -2 3
	// 3 -1 4 2 5
}

private static void dfs(Node n, int k, List<List<Integer>> result) {
		if(n==null)	return;
		List<Integer> list=new ArrayList<Integer>();
		check(n,k,result,list);
		dfs(n.left,k,result);
		dfs(n.right,k,result);
	}

	private static void check(Node n, int k, List<List<Integer>> result, List<Integer> list) {
		if(n==null)	return;
		if(k==n.val){
			List<Integer> temp=new ArrayList<Integer>();
			temp.addAll(list);	temp.add(n.val);
			result.add(temp);
		}
		k=k-n.val;
		list.add(n.val);
		check(n.left, k, result, list);
		check(n.right, k, result, list);
		list.remove(list.size()-1);
	}

From Cracking the coding interview

public int pathsToGivenSum(Node root, int sum) {
		return pathsToGivenSum(root, sum, 0, new HashMap<Integer, Integer>());
	}
	
	private int pathsToGivenSum(Node x, int targetSum, int curSum, HashMap<Integer, Integer> pathCount) {
		if(x == null)
			return 0;
		curSum += x.key;
		int lookUpSum = curSum - targetSum;
		int paths = pathCount.getOrDefault(lookUpSum, 0);
		if (curSum == targetSum)
			paths++;
		incrementHash(pathCount, curSum, 1);
		paths += pathsToGivenSum(x.left, targetSum, curSum, pathCount);
		paths += pathsToGivenSum(x.right, targetSum, curSum, pathCount);
		incrementHash(pathCount, curSum, -1);
		return paths;
	}

	private void incrementHash(HashMap<Integer, Integer> pathCount, int curSum, int delta) {
		int newCount = pathCount.getOrDefault(curSum, 0) + delta;
		if(newCount == 0)
			pathCount.remove(curSum);
		else
			pathCount.put(curSum, newCount);
	}