剑指Offer：面试题25-白红宇

剑指Offer：面试题25

阅读量：4610 次

发布时间：2019-06-09

本文共 2559 字，大约阅读时间需要 8 分钟。

题目描述：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 九度OJ地址： 自己写的代码，自己运行没问题，提交总是不通过 = =

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 #define MAX 100 9 struct BinaryTreeNode{10     int index;11     int value;12     int lchild;13     int rchild;14 };15 16 BinaryTreeNode p[MAX];17 vector
          
            path;18 19 20 void FindPath(BinaryTreeNode* p,int exceptedNum,vector
           
             path,int currentNum){21 currentNum=currentNum+(p->value);22 path.push_back(*p);23 bool IsLeaf=(p->lchild==-1)&&(p->rchild==-1);24 25 if(currentNum==exceptedNum&&IsLeaf)26 {27 printf("A path is found: ");28 vector
            
             ::iterator iter=path.begin();29 for(;iter!=path.end();++iter)30 {31 printf("%d ",iter->index);32 }33 printf("\n");34 }35 if(p->lchild!=-1)36 FindPath(p+(p->lchild-p->index),exceptedNum,path,currentNum);37 if(p->rchild!=-1)38 FindPath(p+(p->rchild-p->index),exceptedNum,path,currentNum);39 currentNum=currentNum-(p->value);40 path.pop_back();41 42 43 }44 void FindPath(BinaryTreeNode* p,int exceptedNum){45 if(p==NULL)46 return;47 int currentNum=0;48 FindPath(p,exceptedNum,path,currentNum);49 50 }51 int main()52 {53 int n,k;54 int v,l,r;55 while(scanf("%d %d",&n,&k)==2)56 {57 memset(p,-1,sizeof(p));58 for(int i=0;i

找了大神代码完美运行：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 100struct BinaryTreeNode{    int index;    int value;    int lchild;    int rchild;};BinaryTreeNode p[MAX];vector
          
            path;void FindPath(BinaryTreeNode* p,int exceptedNum,vector
           
             path,int currentNum){ currentNum=currentNum+(p->value); path.push_back(*p); bool IsLeaf=(p->lchild==-1)&&(p->rchild==-1); if(currentNum==exceptedNum&&IsLeaf) { printf("A path is found: "); vector
            
             ::iterator iter=path.begin(); for(;iter!=path.end();++iter) { printf("%d ",iter->index); } printf("\n"); } if(p->lchild!=-1) FindPath(p+(p->lchild-p->index),exceptedNum,path,currentNum); if(p->rchild!=-1) FindPath(p+(p->rchild-p->index),exceptedNum,path,currentNum); currentNum=currentNum-(p->value); path.pop_back();}void FindPath(BinaryTreeNode* p,int exceptedNum){ if(p==NULL) return; int currentNum=0; FindPath(p,exceptedNum,path,currentNum);}int main(){ int n,k; int v,l,r; while(scanf("%d %d",&n,&k)==2) { memset(p,-1,sizeof(p)); for(int i=0;i