Binary Tree Path Sum - Cracking the coding interview--Q4.8

Cracking the coding interview--Q4.8 - - 博客频道 - CSDN.NET
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，则打印输出。

[MS100]在二元树中找出和为某一值的所有路径（树

    private static void helper(BSTreeNode root, int target, int sum, List<BSTreeNode> list){

        if(root == null){

            if(sum == target){

                for(int i=0; i<list.size(); i++)

                    System.out.print(list.get(i).value + " ");

                System.out.println();

            }

            return;

        }

        sum += root.value;

        list.add(root);

        if(root.left != null){

            helper(root.left, target, sum, list);

        }

        if(root.right != null){

            helper(root.right, target, sum, list);

        }

         

        if(root.left == null && root.right == null){

            helper(null, target, sum, list);

        }

         

        list.remove(root);

    }

     

    public static void printPath(BSTreeNode root, int target){

        if(root == null) return;

        List<BSTreeNode> list = new ArrayList<BSTreeNode>();

        int sum = 0;

        helper(root, target, sum, list);

    }

 public static void findSum(TreeNode head,int sum){
  if(head==null) return;
  TreeNode tnode=head;
  int tmp=0;
  for(int i=1;tnode!=null;i++){
   tmp+=tnode.value;
   if(tmp==sum)
    print(head,i);
   tnode=tnode.parent;
  }
  findSum(head.lchild,sum);
  findSum(head.rchild,sum);
 }
 private static void print(TreeNode tnode,int level){
  Stack<Integer> s=new Stack<Integer>();
  for(int i=0;i<level;i++){
   s.push(tnode.value);
   tnode=tnode.parent;
  }
  while(s.size()>0){
   System.out.print(s.pop()+" ");
  }
 }

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

void print(Node* head, int level){
    vector<int> v;
    for(int i=0; i<level; ++i){
        v.push_back(head->key);
        head = head->parent;
    }
    while(!v.empty()){
        cout<<v.back()<<" ";
        v.pop_back();
    }
    cout<<endl;
}
void find_sum(Node* head, int sum){
    if(head == NULL) return;
    Node *no = head;
    int tmp = 0;
    for(int i=1; no!=NULL; ++i){
        tmp += no->key;
        if(tmp == sum)
            print(head, i);
        no = no->parent;
    }
    find_sum(head->lchild, sum);
    find_sum(head->rchild, sum);
}

http://blog.csdn.net/java_wliang/article/details/41246583

1.     public static void printRoad(TreeNode_4_8 start, int height) {  
2.         int curHeight = 0;  
3.         Stack<Integer> stack = new Stack<Integer>();  
4.           
5.         while(curHeight < height) {  
6.             stack.push(start.data);  
7.             start = start.parent;  
8.             curHeight ++;  
9.         }  
10.           
11.         while(!stack.empty()) {  
12.             System.out.print("  " + stack.pop() + "  ");  
13.         }  
14.     }   
15.     public static void find_sumvalue(TreeNode_4_8 node, int sum) {  
16.         if(node == null) {  
17.             return;  
18.         }  
19.         int curSum = 0;  
20.         TreeNode_4_8 p = node, q;  
21.         int height = 0;  
22.         // 从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空  
23.         while(p != null) {  
24.             curSum += p.data;  
25.             // height 记录层数  
26.             height ++;  
27.             // 如果路径长度等级sum  
28.             if(curSum == sum) {  
29.                 // 打印路径  
30.                 System.out.print("Find path : ");  
31.                 printRoad(node, height);  
32.                 System.out.print("\n");  
33.                 break;  
34.             } else if(curSum > sum){  
35.                 break;  
36.             }  
37.             p = p.parent;  
38.         }  
39.           
40.         find_sumvalue(node.lchild, sum);  
41.         find_sumvalue(node.rchild, sum);  
42.     }  

方案1和方案2的本质思想其实是一样的，不同的只是有无指向父亲结点的指针这个信息。 如果没有这个信息，则需要增加许多额外的空间来存储中间信息。

注意：方案1和方案2代码中的level并非指同一概念，方案1中level表示层数，最小值为1； 方案2中level表示第几层，最小值为0。

LeetCode - Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
LeetCode - Path Sum II |  Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Read full article from Cracking the coding interview--Q4.8 - - 博客频道 - CSDN.NET