首页 > 代码库 > 2016搜狐笔试二叉树和最大的子树

2016搜狐笔试二叉树和最大的子树

2024-08-12 12:18:34   218人阅读

问题描述：

给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？

 

思路：采用自底向上的计算。先计算左右子树总和值，用左右子树的总和加上当前节点值，如果当前总和大于最大值，则更新最大值，同时将最大子树根节点更新为当前根。简单说，就是后序遍历。

 

代码：

[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <limits>  
  3. using namespace std;  
  4.   
  5. struct Node  
  6. {  
  7.     long data;  
  8.     Node *left;  
  9.     Node *right;  
  10. };  
  11.   
  12.   
  13. //  由于要更新最大值和最大子树根，因此采用了引用参数  
  14. //  也可以考虑使用全局变量来处理  
  15. long Max_sub_tree(Node *root , long &max_sum , Node *& sub_root)  
  16. {  
  17.     if(NULL == root)  
  18.     {  
  19.         sub_root = root;  
  20.         return 0;  
  21.     }  
  22.       
  23.       
  24.     //  采用后续遍历  
  25.     long left_sum = Max_sub_tree(root->left , max_sum , sub_root);       //左子树的总和（计算总和过程中可能已经更新了当前的最大值和子树）  
  26.     long right_sum = Max_sub_tree(root->right , max_sum , sub_root); //再计算右子树  
  27.       
  28.     long sum = root->data + left_sum + right_sum;  
  29.     if(sum >= max_sum)  
  30.     {  
  31.         max_sum = sum;  
  32.         sub_root = root;  
  33.     }  
  34.       
  35.     return sum;  
  36. }  
  37.   
  38. int main()  
  39. {  
  40.     Node p = {1,NULL,NULL};  
  41.     Node q = {-3,NULL,NULL};  
  42.     Node lr = {2 , &p , &q};  
  43.     Node rr = {1 , &q , &p};  
  44.     Node r = {5 , &lr , &rr};  
  45.     Node *re = NULL;  
  46.     long max_sum = numeric_limits<long>::min();  
  47.     long sum = Max_sub_tree(&r , max_sum , re);  
  48.     if(NULL == re)  
  49.     {  
  50.         cout<<"empty tree!!!";  
  51.     }  
  52.     else  
  53.     {  
  54.         cout<<"max sum is :"<<max_sum<<endl;  
  55.     }  
  56.     return 0;  
  57. }  

2016搜狐笔试二叉树和最大的子树


联系
我们