首页 > 代码库 > 求二叉树中和为给定值的所有路径
求二叉树中和为给定值的所有路径
转自：http://blog.csdn.net/lalor/article/details/7614381
问题定义：
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)。（ps：关于本程序中建树部分，可以参考：http://blog.csdn.net/lalor/article/details/7613621）
代码实例：
#include <algorithm> #include <iostream> #include <time.h> #include <assert.h> #include <stdio.h> #include <vector> using namespace std; struct node { int data; struct node * lchild; struct node * rchild; }; //将数组转换为深度最低的二叉树，采用了二分查找的思想 struct node* ConvertArrayToTree(int data[], int first, int last) { if (last < first) { return NULL; } else { int mid = ( last + first ) / 2; struct node * newNode = NULL; newNode = (struct node *)malloc(sizeof(struct node)); newNode->data =http://www.mamicode.com/ data[mid]; newNode->lchild = ConvertArrayToTree(data, first, mid - 1); newNode->rchild = ConvertArrayToTree(data, mid + 1, last); return newNode; } } //再最左边插入一个节点 void InsertNodeAtLeft(struct node *root, struct node *newNode) { assert(root != NULL && newNode != NULL); while(root->lchild != NULL) { root = root->lchild; } root->lchild = newNode; } //在最右边插入一个节点 void InsertNodeAtRight(struct node *root, struct node *newNode) { assert(root != NULL && newNode != NULL); while(root->rchild != NULL) { root = root->rchild; } root->rchild = newNode; } //中序遍历 void Traverse(struct node *root) { if (root == NULL) { return; } Traverse(root->lchild); Traverse(root->rchild); printf("%d\t", root->data); } //打印和为sum的路径 void print(vector<int>& buffer, int first, int last) { int i; for (i = first; i <= last; i++) { cout << buffer[i] << "\t"; } cout << endl; } void findSum(struct node *head, int sum, vector<int> &buffer, int level) { if (head == NULL) return; int i; int tmp = sum; buffer.push_back(head->data); for (i = level; i >= 0; i--) { tmp -= buffer[i]; if (tmp == 0) print(buffer, i, level); } vector<int> lbuffer(buffer); vector<int> rbuffer(buffer); findSum(head->lchild, sum, lbuffer, level + 1); findSum(head->rchild, sum, rbuffer, level + 1); } int main(int argc, char* argv[]) { const int SIZE = 10;//测试的数据量 int data[SIZE];//保存数据 int i, j; struct node *head = NULL; for (i = 0; i < SIZE; i++) { data[i] = i + 1; } head = ConvertArrayToTree(data, 0, SIZE - 1); struct node *one = (struct node *)malloc(sizeof(struct node)); struct node *two = (struct node *)malloc(sizeof(struct node)); one->data = http://www.mamicode.com/11; one->lchild = NULL; one->rchild = NULL; two->data = http://www.mamicode.com/4; two->lchild = NULL; two->rchild = NULL; InsertNodeAtLeft(head, one); InsertNodeAtRight(head, two); //遍历数据 // Traverse(head); // printf("\n"); vector<int> v; findSum(head, 14, v, 0); return 0; }
该示例中所使用的二叉树如下所示：
运行结果如下：
求二叉树中和为给定值的所有路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。