寻找树中和为定值的所有路径

2016.8.18改 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. 思路： 一层一层的遍历，保存当前节点到根节点的完整路径，然后从当前节点向上扫描，如果找到了当前节点到某个节点的和等于给定值，则输出之。程序对每个节点都需要遍历一遍，还要扫描当前节点到根节点的路径，且需要保存每个节点到根节点的路径，所以时间复杂度为O（nlgn)，空间复杂度为O(nlgn)。

点击(此处)折叠或打开

#include<iostream> #include<assert.h> #include<vector> #include<malloc.h> using namespace std; struct treeNode {     struct treeNode *pLeft,*pRight;         int p_val; }; struct treeNode *createShortestTree(int *a,int lo,int hi)//构建高度最小的树  二分查找的方法 {     if (lo > hi)//注意着里没有等号,这里不能省略，否则段错误         return NULL;     else     {         int mid = (lo+hi)/2;         int key = a[mid];         struct treeNode *pRoot = NULL;         pRoot = (struct treeNode *)malloc(sizeof(struct treeNode));         pRoot->p_val = key;         pRoot->pLeft = createShortestTree(a,lo,mid-1);         pRoot->pRight = createShortestTree(a,mid+1,hi);         return pRoot;     } } void insetLastLeft(struct treeNode *&pRoot,struct treeNode *pNew) {         assert(pRoot != NULL && pNew != NULL);         struct treeNode *root = pRoot;         while (root->pLeft)         {             root = root->pLeft;         }         root->pLeft = pNew; } void insertLastRight(struct treeNode *&pRoot,struct treeNode *pNew) {     assert(pRoot != NULL && pNew != NULL);//这里别忘了判断pNew     struct treeNode *root = pRoot;     while (root->pRight)     {         root = root->pRight;     }     root->pRight = pNew; } void print(vector<int> buffer,int first,int last)//顺序打印 {     for (int i = first;i <= last;i++)     {         cout << buffer[i]<< "\t";     }     cout << "\n"; } void findsum(struct treeNode *pRoot,int sum,vector<int> &buffer,int level) {     if (pRoot == NULL) return ;//这个终止条件别忘写了     int tmp = sum;     int i = 0;     buffer.push_back(pRoot->p_val);     for (i = level;i >= 0;i--)     {         tmp -= buffer[i];         if (tmp == 0) print(buffer,i,level);     }     vector<int> bufferl(buffer);//buffer1[0] = buffer[0],bufferl[1] = 新加入的节点的值....     vector<int> bufferr(buffer);     findsum(pRoot->pLeft,sum,bufferl,level+1);     findsum(pRoot->pRight,sum,bufferr,level+1); } int main() {     int i = 0;     int a[10];     vector<int> vec;     for (i = 0;i < 10;i++)     {         a[i] = i+1;     }     struct treeNode *pRoot = NULL;     pRoot = createShortestTree(a,0,9);     if (pRoot == NULL)     {         cout << "pRoot is null" << endl;     }     struct treeNode *new1 = (struct treeNode *)malloc(sizeof(struct treeNode));     new1->p_val = 11;     new1->pLeft = NULL;     new1->pRight = NULL;     struct treeNode *new2 = (struct treeNode *)malloc(sizeof(struct treeNode));     new2->p_val = 4;     new2->pLeft = NULL;     new2->pRight = NULL;     insetLastLeft(pRoot,new1);     insertLastRight(pRoot,new2);     findsum(pRoot,14,vec,0);     return 0; } 运行结果: [root@localhost c++]# ./a.out 2       1       11 5       2       3       4 8       6 10      4 <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(362) | 评论(0) | 转发(0) | 0

上一篇：树的一些基本操作(遍历，构造，高度，节点数，销毁)

下一篇：寻找和为定值的多个数

相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议