劍指OFFER之二叉樹中和為某一值的路徑（九度OJ1368）

題目描述：

輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

 

輸入：

每個測試案例包括n+1行：

第一行為2個整數n，k(1<=n<=10000)，n表示結點的個數，k表示要求的路徑和，結點編號從1到n。                                                                                                       

接下來有n行。這n行中每行為3個整數vi,leftnode,rightnode，vi表示第i個結點的值，leftnode表示第i個結點的左孩子結點編號，rightnode表示第i個結點的右孩子結點編號，若無結點值為-1。編號為1的結點為根結點。

 

輸出：

對應每個測試案例，先輸出“result:”占一行，接下來按字典順序輸出滿足條件的所有路徑，這些路徑由結點編號組成，輸出格式參照輸出樣例。

 

樣例輸入：

5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1

樣例輸出：

result:
A path is found: 1 2 5
A path is found: 1 3
result:

解題思路：

　　首先注意題目的兩點要求，

　　1 路徑：從根一直到葉子，所有的節點之和是 輸入的第二個數。

　　2 按字典順序，也就是1在2的前面，比如兩條路徑 124 13，那麼就得是124 13的順序輸出，而不能使13 124的順序。

　　做題思路方面：

　　1 在構造樹的時候，左右子樹按大小來，保證左孩子比右孩子大，這樣我們在掃描的時候，可以按照左子樹優先來掃描，保證按字典順序輸出。

for(i=1;i<=n;i++){
            int l,r;
            scanf("%d %d %d",&a->arr[i].num, &l, &r);
            if(l<r){
                a->arr[i].lchild = l;
                a->arr[i].rchild = r;
            }else{
                a->arr[i].lchild = r;
                a->arr[i].rchild = l;
            }
        }

　　2 很簡單，用棧存儲讀取過的節點元素，我們這裡有個技巧，在函數內部，因為使用形參，而子函數不會對這個形參發生作用，因此，考慮用形參k來標記，是樹的第幾層，而使用top來當做棧頂。

　　3 我們從根開始遍歷，知道最後葉子時，如果滿足條件，則輸出：

if(test_sum == sum && a->arr[id].lchild==-1 && a->arr[id].rchild==-1 ){
        printf("A path is found:");
        int i;
        for(i=0;i<top;i++)
            printf(" %d", route[i] );
        printf("\n");
    }

全部代碼：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAXSIZE 10005
typedef struct treenode{
    int num;
    int lchild;
    int rchild;
}Tree;
typedef struct treearr{
    struct treenode arr[MAXSIZE];
}treeArr;
 
int route[MAXSIZE]={0};
int top=0;
 
void traceTree(treeArr *a,int id,int sum,int sum_tmp,int n);
 
int main(){
    int n,i,sum;
    while(scanf("%d %d",&n,&sum)!=EOF){
        treeArr *a = (treeArr *)malloc(sizeof(treeArr));
         
        for(i=1;i<=n;i++){
            int l,r;
            scanf("%d %d %d",&a->arr[i].num, &l, &r);
            if(l<r){
                a->arr[i].lchild = l;
                a->arr[i].rchild = r;
            }else{
                a->arr[i].lchild = r;
                a->arr[i].rchild = l;
            }
        }
        printf("result:\n");
        memset(&route,0,sizeof(int)*MAXSIZE);
        top = 0;
        traceTree(a,1,sum,0,1);
    }
    return 0;
}
void traceTree(treeArr *a,int id,int sum,int sum_tmp,int k){
    if(id == -1 || sum_tmp+a->arr[id].num > sum)
        return ;
    int test_sum = sum_tmp+a->arr[id].num;
    route[top++] = id;
    if(test_sum == sum && a->arr[id].lchild==-1 && a->arr[id].rchild==-1 ){
        printf("A path is found:");
        int i;
        for(i=0;i<top;i++)
            printf(" %d", route[i] );
        printf("\n");
    }
    traceTree(a,a->arr[id].lchild,sum,test_sum,k+1);
    top = k; 
    traceTree(a,a->arr[id].rchild,sum,test_sum,k+1); 
}
/**************************************************************
    Problem: 1368
    User: xhalo
    Language: C
    Result: Accepted
    Time:40 ms
    Memory:3296 kb
****************************************************************/