求二叉树的最大子树

max_subtree.cc

//a binary tree, each node is positive or negative integer, how to find a sub-tree, all the nodes sum is largest.

#include <iostream>
#include <limits>

using namespace std;

struct Node {
    long data;
    Node *lchild;
    Node *rchild;
};

pair<long, bool> maxSubtree(Node *root, bool positiveOnly, long& maxSum, Node *& maxNode)
{
    long sum = 0;
    if (root == NULL) {
        maxNode = root;
        return make_pair(0, true);
    }
    pair<long, bool> left = maxSubtree(root->lchild, positiveOnly, maxSum, maxNode);
    pair<long, bool> right = maxSubtree(root->rchild, positiveOnly, maxSum, maxNode);
    sum = root->data + left.first + right.first;
    if (positiveOnly) {
        if (root->data > 0 && left.second && right.second) {
            if (sum >= maxSum) {
                maxSum = sum;
                maxNode = root;
            }
        }
    } else {
        if (sum >= maxSum) {
            maxSum = sum;
            maxNode = root;
        }
    }
    return make_pair(sum, (root->data > 0) && left.second && right.second);
}

  Node* makeTree(int arr[], int currentIndex, int len){
      if (NULL == arr || len <= 0)
          return NULL;
 
      if (currentIndex < len){
          Node* pnode = new Node;
          pnode->data = arr[currentIndex];
 
          if (2*currentIndex < len)
              pnode->lchild = makeTree(arr, 2*currentIndex, len);
          else
              pnode->lchild = NULL;
 
          if (2*currentIndex + 1 < len)
              pnode->rchild = makeTree(arr, 2*currentIndex + 1, len);
          else
              pnode->rchild = NULL;
 
          return pnode;
      } else
          return NULL;
  }
 
  void destroyTree(Node* head){
      if (NULL == head)
          return;
      if (head->lchild)
          destroyTree(head->lchild);
      if (head->rchild)
          destroyTree(head->rchild);
 
      delete head;
  }
 
  void tranverseTree(Node* head){
      if (NULL == head)
          return;
      tranverseTree(head->lchild);
      cout << " " << head->data << " ";
      tranverseTree(head->rchild);
  }
 
  int main(){
      long max_sum = 0;
      Node* max_node = NULL;
      int tree[] = {0, 1, 3, -8, 10, 2, -9, 6, 4, 12, -15, 20, 7, -2, 9};
      copy(tree,
           tree + sizeof(tree)/sizeof(tree[0]),
           ostream_iterator<int>(cout, " "));
      cout << endl;
     Node* head = makeTree(tree, 1, sizeof(tree)/(sizeof(tree[0])));

     tranverseTree(head);
     cout << endl;

     pair<long, bool> ret = maxSubTree(head, true, max_sum, max_node);
     if (NULL == max_node)
         cout << "The tree is empty or there is no such subtree" << endl;
     cout << "the max subtree " << max_sum << endl;

     destroyTree(head);
     return 0;
 }