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.

CC150-4.9.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 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.
	 * 
	 * 
	 *  @Runtime & spaces
	 * 	runtime: o(nlogn) for start from anywhere, O(logn) for start from root
	 * 	space: O(logn) 用数组来记录，subsrcript用的是节点的level
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		
	TreeNode root = new TreeNode(7);
        root.left = new TreeNode(10);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(1);
        root.right.left = new TreeNode(8);
        root.right.left.left = new TreeNode(11);	
        so.allPaths(root, 14);
	}
	public void allPaths(TreeNode root, int sum){
		if(root==null)
			return;
		int depth=depth(root);
		int[] path=new int[depth];
		findPaths(root,sum,path,0);
	}
	private void findPaths(TreeNode root, int sum, int[] path, int level) {
		// TODO Auto-generated method stub
		if(root==null)
			return;
		path[level]=root.val;
		int temp=0;
		//从level开始往上加！！
		for(int i=level;i>=0;i--){
			temp+=path[i];
			if(temp==sum){
				printPath(path,i,level);
			}
		}
		findPaths(root.left, sum, path, level+1);
		findPaths(root.right, sum, path, level+1);
	}
	private void printPath(int[] path, int i, int level) {
		// TODO Auto-generated method stub
		System.out.print(path[i]);
		for(int j=i+1;j<=level;j++){
			System.out.print(" -> "+path[j]);
		}
		System.out.println();
	}
	private int depth(TreeNode root) {
		// TODO Auto-generated method stub
		if(root==null)
			return 0;
		return 1+Math.max(depth(root.left), depth(root.right));
	}
}