cc150-4.9

PathSum.java

public class PathSum {
	
	public static void main(String args[] ) {
		TreeNode n3 = new TreeNode(3, null, null);
		TreeNode n1 = new TreeNode(1, null, null);
		TreeNode n2 = new TreeNode(5, null, null);
		TreeNode n10 = new TreeNode(10, null, null);
		TreeNode n4 = new TreeNode(4, n3, null);
		TreeNode n6 = new TreeNode(6, n4, n1);
		TreeNode n9 = new TreeNode(9, null, n10);
		TreeNode n8 = new TreeNode(8, null, n9);
		TreeNode n5 = new TreeNode(5, n2, n8);
		TreeNode n7 = new TreeNode(7, n6, n5);
		
		findSumPath(n7, 17);
		
	}
	
	public static void findSumPath(TreeNode root, int sum) {
		
		int depth = depth(root);
		int path[] = new int[depth];
		
		findSumPath(root, sum, path, 0);
		
	}
	
	public static void findSumPath(TreeNode root, int sum, int[] path, int level){
		
		if(root == null) {
			return;
		}
		
		sum = sum - root.item;
		path[level] = root.item;
		
		if(sum == 0) {
			//print path from 0 to current level
			
			for(int i=0; i<=level; i++){
				System.out.print(path[i] + "->");
			}
			System.out.println("");
			
		}
		
		findSumPath(root.leftNode, sum, path, level+1);
		findSumPath(root.rightNode, sum, path, level+1);
		
	}
	
	public static int depth(TreeNode root){
		if (root == null) {
			return 0;
		}
		
		int depthOfChild = Math.max(depth(root.leftNode), depth(root.rightNode));
		
		return depthOfChild + 1;
	}

}