问题描述：

 

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

 

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

 

代码：

               #include <iostream>          #include <limits>          using namespace std;                    struct Node          {              long data;              Node *left;              Node *right;          };                              //  由于要更新最大值和最大子树根，因此采用了引用参数          //  也可以考虑使用全局变量来处理          long Max_sub_tree(Node *root , long &max_sum , Node *& sub_root)          {              if(NULL == root)              {                  sub_root = root;                  return 0;              }                                          //  采用后续遍历              long left_sum = Max_sub_tree(root->left , max_sum , sub_root);       //左子树的总和（计算总和过程中可能已经更新了当前的最大值和子树）              long right_sum = Max_sub_tree(root->right , max_sum , sub_root); //再计算右子树                            long sum = root->data + left_sum + right_sum;              if(sum >= max_sum)              {                  max_sum = sum;                  sub_root = root;              }                            return sum;          }                    int main()          {              Node p = {1,NULL,NULL};              Node q = {-3,NULL,NULL};              Node lr = {2 , &p , &q};              Node rr = {1 , &q , &p};              Node r = {5 , &lr , &rr};              Node *re = NULL;              long max_sum = numeric_limits<long>::min();              long sum = Max_sub_tree(&r , max_sum , re);              if(NULL == re)              {                  cout<<"empty tree!!!";              }              else              {                  cout<<"max sum is :"<<max_sum<<endl;              }              return 0;          }
#include <iostream>
#include <limits>
using namespace std;

struct Node
{
    long data;
    Node *left;
    Node *right;
};


//  由于要更新最大值和最大子树根，因此采用了引用参数
//  也可以考虑使用全局变量来处理
long Max_sub_tree(Node *root , long &max_sum , Node *& sub_root)
{
    if(NULL == root)
    {
        sub_root = root;
        return 0;
    }


    //  采用后续遍历
    long left_sum = Max_sub_tree(root->left , max_sum , sub_root);       //左子树的总和（计算总和过程中可能已经更新了当前的最大值和子树）
    long right_sum = Max_sub_tree(root->right , max_sum , sub_root); //再计算右子树

    long sum = root->data + left_sum + right_sum;
    if(sum >= max_sum)
    {
        max_sum = sum;
        sub_root = root;
    }

    return sum;
}

int main()
{
    Node p = {1,NULL,NULL};
    Node q = {-3,NULL,NULL};
    Node lr = {2 , &p , &q};
    Node rr = {1 , &q , &p};
    Node r = {5 , &lr , &rr};
    Node *re = NULL;
    long max_sum = numeric_limits<long>::min();
    long sum = Max_sub_tree(&r , max_sum , re);
    if(NULL == re)
    {
        cout<<"empty tree!!!";
    }
    else
    {
        cout<<"max sum is :"<<max_sum<<endl;
    }
    return 0;
}