求二叉树中和为给定值的所有路径
求二叉树中和为给定值的所有路径
问题定义:
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:关于本程序中建树部分,可以参考: )
代码实例:
- #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 = 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 = 11;
- one->lchild = NULL;
- one->rchild = NULL;
- two->data = 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;
- }
运行结果如下:
评论暂时关闭