Skip to content

Instantly share code, notes, and snippets.

@esyrt

esyrt/max_subtree.cc

Forked from luangong/maximum_subtree.cc
Created September 18, 2012 05:26
Show Gist options
  • Save esyrt/3741421 to your computer and use it in GitHub Desktop.
Save esyrt/3741421 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @luangong luangong revised this gist Sep 18, 2012. 1 changed file with 10 additions and 10 deletions.
    20 changes: 10 additions & 10 deletions max_subtree.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -9,15 +9,15 @@ struct Node {
    Node *rchild;
    };

    int maxSubtree(Node *root, int& maxSum, Node *& maxNode)
    long maxSubtree(Node *root, long& maxSum, Node *& maxNode)
    {
    int sum = 0;
    long sum = 0;
    if (root == NULL) {
    maxNode = root;
    return 0;
    }
    int leftSum = maxSubtree(root->lchild, maxSum, maxNode);
    int rightSum = maxSubtree(root->rchild, maxSum, maxNode);
    long leftSum = maxSubtree(root->lchild, maxSum, maxNode);
    long rightSum = maxSubtree(root->rchild, maxSum, maxNode);
    sum = root->data + leftSum + rightSum;
    if (sum >= maxSum) {
    maxSum = sum;
    @@ -28,15 +28,15 @@ int maxSubtree(Node *root, int& maxSum, Node *& maxNode)

    int main()
    {
    int maxSum = numeric_limits<int>::min();
    long maxSum = numeric_limits<long>::min();
    Node *maxNode;
    Node q = { -4, NULL, NULL };
    Node r = { 5, NULL, NULL };
    Node p = { 3, &q, &r };
    int result = maxSubtree(&p, maxSum, maxNode);
    Node q = { 2000000000, NULL, NULL };
    Node r = { 1000000000, NULL, NULL };
    Node p = { 2000000000, &q, &r };
    long result = maxSubtree(&p, maxSum, maxNode);
    if (maxNode == NULL)
    cout << "The tree is empty!" << endl;
    else
    cout << maxSum << ", " << maxNode << endl;
    return 0;
    }
    }
  2. @luangong luangong revised this gist Sep 18, 2012. 1 changed file with 5 additions and 2 deletions.
    7 changes: 5 additions & 2 deletions max_subtree.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -34,6 +34,9 @@ int main()
    Node r = { 5, NULL, NULL };
    Node p = { 3, &q, &r };
    int result = maxSubtree(&p, maxSum, maxNode);
    cout << maxSum << ", " << maxNode << endl;
    if (maxNode == NULL)
    cout << "The tree is empty!" << endl;
    else
    cout << maxSum << ", " << maxNode << endl;
    return 0;
    }
    }
  3. @luangong luangong revised this gist Sep 18, 2012. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion max_subtree.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -12,8 +12,10 @@ struct Node {
    int maxSubtree(Node *root, int& maxSum, Node *& maxNode)
    {
    int sum = 0;
    if (root == NULL)
    if (root == NULL) {
    maxNode = root;
    return 0;
    }
    int leftSum = maxSubtree(root->lchild, maxSum, maxNode);
    int rightSum = maxSubtree(root->rchild, maxSum, maxNode);
    sum = root->data + leftSum + rightSum;
  4. @luangong luangong revised this gist Sep 18, 2012. 1 changed file with 8 additions and 17 deletions.
    25 changes: 8 additions & 17 deletions max_subtree.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,6 @@
    #include <iostream>
    #include <limits>

    using namespace std;

    struct Node {
    @@ -14,8 +16,8 @@ int maxSubtree(Node *root, int& maxSum, Node *& maxNode)
    return 0;
    int leftSum = maxSubtree(root->lchild, maxSum, maxNode);
    int rightSum = maxSubtree(root->rchild, maxSum, maxNode);
    sum += root->data + leftSum + rightSum;
    if (sum > maxSum) {
    sum = root->data + leftSum + rightSum;
    if (sum >= maxSum) {
    maxSum = sum;
    maxNode = root;
    }
    @@ -26,21 +28,10 @@ int main()
    {
    int maxSum = numeric_limits<int>::min();
    Node *maxNode;
    Node *q = new Node;
    q->data = -4;
    q->lchild = q->rchild = NULL;
    Node *r = new Node;
    r->data = 5;
    r->lchild = r->rchild = NULL;
    Node *p = new Node;
    p->data = 3;
    p->lchild = q;
    p->rchild = r;
    int result = maxSubtree(p, maxSum, maxNode);
    r->data = 5;
    Node q = { -4, NULL, NULL };
    Node r = { 5, NULL, NULL };
    Node p = { 3, &q, &r };
    int result = maxSubtree(&p, maxSum, maxNode);
    cout << maxSum << ", " << maxNode << endl;
    delete q;
    delete r;
    delete p;
    return 0;
    }
  5. @luangong luangong created this gist Sep 18, 2012.
    46 changes: 46 additions & 0 deletions max_subtree.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    #include <iostream>
    using namespace std;

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

    int maxSubtree(Node *root, int& maxSum, Node *& maxNode)
    {
    int sum = 0;
    if (root == NULL)
    return 0;
    int leftSum = maxSubtree(root->lchild, maxSum, maxNode);
    int rightSum = maxSubtree(root->rchild, maxSum, maxNode);
    sum += root->data + leftSum + rightSum;
    if (sum > maxSum) {
    maxSum = sum;
    maxNode = root;
    }
    return sum;
    }

    int main()
    {
    int maxSum = numeric_limits<int>::min();
    Node *maxNode;
    Node *q = new Node;
    q->data = -4;
    q->lchild = q->rchild = NULL;
    Node *r = new Node;
    r->data = 5;
    r->lchild = r->rchild = NULL;
    Node *p = new Node;
    p->data = 3;
    p->lchild = q;
    p->rchild = r;
    int result = maxSubtree(p, maxSum, maxNode);
    r->data = 5;
    cout << maxSum << ", " << maxNode << endl;
    delete q;
    delete r;
    delete p;
    return 0;
    }