求tree中節點之間路徑總和等于給定數值的算法

原題目：

Given a tree (any tree, in this code, i define the tree as a binary tree) and a integer value, please calculate and print the nodes if their total case is equal the given integer value.   Fg.

treehead-> A{1}

                     /    \

               B{2}  C{1}

                /           \

             D{0}     E{2}

          /                \

          F{1} 

the function signature is blow:  void calculatePath(node* treehead, int cost)

if given tree and integer as below:   calculatePath(treehead, 4)  this function will print out:     F + D + B + A = 4    E + C + A = 4

if given integer is : 2, the print out will be like this:   D + B = 2   C + A = 2 

Here is my implementation for your reference:  struct node  { node* parent; node* left; node* right; char name; int cost; };

void printNodesBetween(node* parent, node* child, int cost) { if (child == NULL || parent == NULL) return;

node* tempChild = child; while (tempChild!= parent ) { printf("%c + ", tempChild->name); tempChild = tempChild->parent; } printf ("%c = %d \n", tempChild->name, cost); }

void calculatePathBetween(node* parent, node* child, int cost) { if (child == NULL) return;

node* tempParent = parent; int totalCost = child->cost; while (tempParent != NULL) { totalCost += tempParent->cost; if (totalCost == cost) { printNodesBetween(tempParent, child, cost); }

tempParent = tempParent->parent; }

calculatePathBetween(child, child->left, cost); calculatePathBetween(child, child->right, cost); }

void calculatePath(node* treehead, int cost) { if (treehead == NULL) { return; }

calculatePathBetween(treehead, treehead->left, cost); calculatePathBetween(treehead, treehead->right, cost);

}