Cracking the coding interview--Q4.8

原文：

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

译文：

给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径： 路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。

如果结点中包含指向父亲结点的指针，那么，只需要去遍历这棵二叉树， 然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空(这个具有唯一性， 因为每个结点都只有一个父亲结点。也正因为这个唯一性， 可以不另外开额外的空间来保存路径)，如果等于给定的值sum，则打印输出。

package chapter_4_TreesandGraphs;

import java.util.Scanner;
import java.util.Stack;

/**
 *
 * 二叉树节点信息
 * 
 */
class TreeNode_4_8 {
	public int data;
	public TreeNode_4_8 lchild;
	public TreeNode_4_8 rchild;
	public TreeNode_4_8 parent;
}

/**
 * 
 * 给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径： 路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。
 *
 */
public class Question_4_8 {

	/**
	 * @param array
	 * @return
	 * 
	 * 按照层次创建二叉树
	 * 
	 */
	public static TreeNode_4_8 createTree(int array[]) {
		TreeNode_4_8 root = new TreeNode_4_8();
		int len = array.length;
		int curIndex = 0;
		if(len == 0) {
			return null;
		}
		root.data = array[curIndex ++];
		TreeNode_4_8[] queue = new TreeNode_4_8[len];
		int head = 0;
		int tail = 0;
		queue[tail++] = root;
		// 遍历数据结点信息，使用队列记录二叉树结点信息
		while(curIndex < len) {
			TreeNode_4_8 parent = queue[head++];
			
			int value = array[curIndex++];
			TreeNode_4_8 left = new TreeNode_4_8();
			left.data = value;
			left.parent = parent;
			
			parent.lchild = left;
			queue[tail++] = left;
			if(curIndex < len) {
				value = array[curIndex++];
				TreeNode_4_8 right = new TreeNode_4_8();
				right.data = value;
				right.parent = parent;
				
				parent.rchild = right;
				queue[tail++] = right;
			}
		}
		
		return root;
	}
	
	/**
	 * @param node
	 * 
	 * 先序递归遍历二叉树
	 * 
	 */
	public static void preOrderTraverse(TreeNode_4_8 node) {
		if(node != null) {
			System.out.print(" " + node.data + " ");
			preOrderTraverse(node.lchild);
			preOrderTraverse(node.rchild);
		}
	}
	
	public static void printRoad(TreeNode_4_8 start, int height) {
		int curHeight = 0;
		Stack<Integer> stack = new Stack<Integer>();
		
 		while(curHeight < height) {
 			stack.push(start.data);
			start = start.parent;
			curHeight ++;
		}
 		
 		while(!stack.empty()) {
 			System.out.print("  " + stack.pop() + "  ");
 		}
	}
	
	/**
	 * @param node
	 * @param sum
	 * 
	 * 如果结点中包含指向父亲结点的指针
	 * 
	 * 先序遍历二叉树，然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空，
	 * 如果等于给定的值sum，则打印输出。
	 * 
	 */
	public static void find_sumvalue(TreeNode_4_8 node, int sum) {
		if(node == null) {
			return;
		}
		int curSum = 0;
		TreeNode_4_8 p = node, q;
		int height = 0;
		// 从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空
		while(p != null) {
			curSum += p.data;
			// height 记录层数
			height ++;
			// 如果路径长度等级sum
			if(curSum == sum) {
				// 打印路径
				System.out.print("Find path : ");
				printRoad(node, height);
				System.out.print("\n");
				break;
			} else if(curSum > sum){
				break;
			}
			p = p.parent;
		}
		
		find_sumvalue(node.lchild, sum);
		find_sumvalue(node.rchild, sum);
	} 
	
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		// 2 3 4 2 1 1 0 8 2 1 4 0 0 1 1
		// 7
		String string = scanner.nextLine();
		int sum = scanner.nextInt();
		scanner.nextLine();
		
		String data[] = string.split(" ");
		int array[] = new int[data.length];
		for(int i=0; i< data.length; i++) {
			array[i] = Integer.parseInt(data[i]);
		}
		
		TreeNode_4_8 root = createTree(array);
		
		System.out.print("先序遍历 ：");
		preOrderTraverse(root);
		System.out.print("\n");
		System.out.print("遍历找出路径长度 ：\n");
		find_sumvalue(root, sum);
		System.out.print("\n");
	}
}