求二叉树的最大子树

maximum_subtree.cc

#include <iostream>
#include <limits>


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


std::pair<long, bool> maxSubtree(
    Node *root, bool positiveOnly, long& maxSum, Node *& maxNode) {
  long sum = 0;
  if (root == nullptr) {
    maxNode = root;
    return std::make_pair(0, true);
  }
  std::pair<long, bool> left = maxSubtree(root->lchild, positiveOnly, maxSum, maxNode);
  std::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 std::make_pair(sum, (root->data > 0) && left.second && right.second);
}

// Program entry-point.
int main(int argc, char **argv) {
  long maxSum = std::numeric_limits<long>::min();
  Node *maxNode;
  Node q = {-4, nullptr, nullptr};
  Node r = {3, nullptr, nullptr};
  Node p = {5, &q, &r};
  std::pair<long, bool> result = maxSubtree(&p, true, maxSum, maxNode);
  if (maxNode == nullptr) {
    std::cout << "The tree is empty or there is no such subtree!" << std::endl;
  } else {
    std::cout << maxSum << ", " << maxNode << std::endl;
  }
  return 0;
}