微软面试4、在二元树中找出和为某一值的所有路径

题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
10
/ /
5 12
/ /
4 7
则打印出两条路径：10, 12和10, 5, 7。

思路1：（这个感觉不是最好的，看到的欢迎分享新方法）

后续遍历二叉树，同时用一个变量sum记录栈中所有节点的和，当节点输出时，判断该节点是否是叶子节点，同时sum是否是目标和

若两者均满足，则测试栈中的元素即是一条路径。

代码：

 1 View Code 
 2  void PathSum(BiTree BT,int SUM){
 3      Stack tag;//标记栈
 4      Stack S;//树节点栈
 5      Stack temp;//用来输出的
 6      int sum=0;
 7      BinTree p=BT;
 8      while(p!=NULL||!isEmptyStack(S)){
 9          while(p!=NULL){
10               Push(S,p);
11               sum+=p->data;
12               Push(tag,0);
13               p=p->lchild;
14          }
15          if(Top(tag)==1){
16                 p=Top(S)
17                 if(sum==SUM&&p->lchiled==NULL&&prchild==NULL){
18                        while（isEmptyStack(S)）{
19                               push(temp,Top(S));
20                               pop(S);
21                         }
22                         while(isEmptyStack(temp)){
23                               BinTree x=Top(temp);
24                               printf("%d",x->data);
25                               push(S,x);
26                               pop(temp);
27                          }
28                  }
29                  BinTree x=Top(S);
30                  Sum-=x->data;
31                  Pop(S);
32                  Pop(tag);
33                  p=NULL;
34          }else{
35               p=Top(S);
36               p=p->rchild;
37               Top(tag)->data=1;
38          }
39      }
40  }

思路2：深度优先搜索，用队列保存节点（这个暂时写不出来代码，看完深度优先搜索后给出）