Massive Algorithms: 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

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() + " ");
}
}
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);
}

方案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

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

Labels

Popular Posts