歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

求二叉樹中和為給定值的所有路徑


問題定義:

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://www.linuxidc.com/Linux/2012-05/61459.htm )

代碼實例:

  1. #include <algorithm>   
  2. #include <iostream>   
  3. #include <time.h>   
  4. #include <assert.h>   
  5. #include <stdio.h>   
  6. #include <vector>   
  7.   
  8.   
  9. using namespace std;  
  10.   
  11. struct node   
  12. {  
  13.     int data;  
  14.     struct node * lchild;  
  15.     struct node * rchild;  
  16. };  
  17.   
  18.   
  19. //將數組轉換為深度最低的二叉樹,采用了二分查找的思想   
  20. struct node* ConvertArrayToTree(int data[], int first, int last)  
  21. {  
  22.     if (last < first)   
  23.     {  
  24.         return NULL;  
  25.     }  
  26.     else  
  27.     {  
  28.         int mid = ( last + first ) / 2;  
  29.         struct node * newNode = NULL;  
  30.         newNode = (struct node *)malloc(sizeof(struct node));  
  31.         newNode->data = data[mid];  
  32.         newNode->lchild = ConvertArrayToTree(data, first, mid - 1);  
  33.         newNode->rchild = ConvertArrayToTree(data, mid + 1, last);  
  34.         return newNode;  
  35.     }  
  36. }  
  37.   
  38. //再最左邊插入一個節點   
  39. void InsertNodeAtLeft(struct node *root, struct node *newNode)  
  40. {  
  41.     assert(root != NULL && newNode != NULL);  
  42.     while(root->lchild != NULL)  
  43.     {  
  44.         root = root->lchild;  
  45.     }  
  46.     root->lchild = newNode;  
  47. }  
  48.   
  49. //在最右邊插入一個節點   
  50. void InsertNodeAtRight(struct node *root, struct node *newNode)  
  51. {  
  52.     assert(root != NULL && newNode != NULL);  
  53.     while(root->rchild != NULL)  
  54.     {  
  55.         root = root->rchild;  
  56.     }  
  57.     root->rchild = newNode;  
  58. }  
  59. //中序遍歷   
  60. void Traverse(struct node *root)  
  61. {  
  62.     if (root == NULL)   
  63.     {  
  64.         return;  
  65.     }  
  66.     Traverse(root->lchild);  
  67.     Traverse(root->rchild);  
  68.     printf("%d\t", root->data);  
  69. }  
  70.   
  71. //打印和為sum的路徑   
  72. void print(vector<int>& buffer, int first, int last)  
  73. {  
  74.     int i;  
  75.     for (i = first; i <= last; i++)   
  76.     {  
  77.         cout << buffer[i] << "\t";  
  78.     }  
  79.     cout << endl;  
  80. }  
  81. void findSum(struct node *head, int sum, vector<int> &buffer, int level)  
  82. {  
  83.     if (head == NULL) return;  
  84.   
  85.     int i;  
  86.     int tmp = sum;  
  87.     buffer.push_back(head->data);  
  88.     for (i = level; i >= 0; i--)  
  89.     {  
  90.         tmp -= buffer[i];  
  91.         if (tmp == 0) print(buffer, i, level);  
  92.     }  
  93.   
  94.     vector<int> lbuffer(buffer);  
  95.     vector<int> rbuffer(buffer);  
  96.   
  97.     findSum(head->lchild, sum, lbuffer, level + 1);  
  98.     findSum(head->rchild, sum, rbuffer, level + 1);  
  99. }  
  100.   
  101. int main(int argc, char* argv[])  
  102. {  
  103.     const int SIZE = 10;//測試的數據量   
  104.     int data[SIZE];//保存數據   
  105.     int i, j;  
  106.     struct node *head = NULL;  
  107.   
  108.     for (i = 0; i < SIZE; i++)   
  109.     {  
  110.         data[i] = i + 1;  
  111.     }  
  112.   
  113.     head = ConvertArrayToTree(data, 0, SIZE - 1);  
  114.   
  115.     struct node *one = (struct node *)malloc(sizeof(struct node));  
  116.     struct node *two = (struct node *)malloc(sizeof(struct node));  
  117.     one->data = 11;  
  118.     one->lchild = NULL;  
  119.     one->rchild = NULL;  
  120.       
  121.     two->data = 4;  
  122.     two->lchild = NULL;  
  123.     two->rchild = NULL;  
  124.   
  125.     InsertNodeAtLeft(head, one);  
  126.     InsertNodeAtRight(head, two);  
  127.     //遍歷數據   
  128. //  Traverse(head);   
  129. //  printf("\n");   
  130.     vector<int> v;  
  131.     findSum(head, 14, v, 0);  
  132.     return 0;  
  133. }  
該示例中所使用的二叉樹如下所示:


運行結果如下:

Copyright © Linux教程網 All Rights Reserved