fork download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int ans = 0;
  5.  
  6. struct Node{
  7.         int data;
  8.         struct Node* left;
  9.         struct Node* right;
  10.         struct Node* maxnode;
  11.         Node(int val, Node* l = NULL, Node* r = NULL,Node* maxn=NULL){
  12.                 data = val;
  13.                 left = l;
  14.                 right = r;
  15.                 maxnode=maxn;
  16.         }
  17. };
  18.  
  19. class BinaryTree{
  20.         Node* Root;
  21.         Node* X;
  22.         Node* Y;
  23.  
  24.         public:
  25.         BinaryTree(){
  26.                 Root = NULL;
  27.         }
  28.         void Construct(){
  29.                 Node* h = new Node(1);
  30.                 Node* i = new Node(2);
  31.                 Node* j = new Node(1000);
  32.                 Node* k = new Node(2000);
  33.                 Node* l = new Node(1);
  34.                 Node* m = new Node(2);
  35.                 Node* n = new Node(1);
  36.                 Node* o = new Node(2);
  37.                 Node* d = new Node(1,h,i);
  38.                 Node* e = new Node(100,j,k);
  39.                 Node* f = new Node(1,l,m);
  40.                 Node* g = new Node(2,n,o);
  41.                 Node* b = new Node(100,d,e);
  42.                 Node* c = new Node(1,f,g);
  43.                 Node* a = new Node(100,b,c);
  44.                 Root = a;
  45.         }
  46.  
  47.         bool isleaf(Node *temp)
  48.         {
  49.             if(temp==NULL)
  50.                 return false;
  51.             if(temp->left==NULL && temp->right==NULL)
  52.                 return true;
  53.             return false;
  54.         }
  55.  
  56.         void printX()
  57.         {
  58.             cout<<"X: "<<X->data<<endl;
  59.         }
  60.  
  61.         void printY()
  62.         {
  63.             cout<<"Y: "<<Y->data<<endl;
  64.         }
  65.  
  66.         void PrintInOrder(Node *temp){
  67.                 if(temp != NULL){
  68.                         PrintInOrder(temp -> left);
  69.                         cout << temp -> data << endl;
  70.                         PrintInOrder(temp -> right);            
  71.                 }
  72.         }
  73.  
  74.         void PrintBT(){
  75.                 PrintInOrder(Root);
  76.         }
  77.  
  78.         void Solve(){
  79.                 Solve(Root,0);
  80.         }
  81.  
  82.         int Solve(Node *curr, int sumFromParent){
  83.                 if(curr == NULL) return 0;
  84.  
  85.                 int sumFromRootToCurr = sumFromParent + curr -> data;
  86.                 int lMaxFromLeaf = Solve(curr -> left, sumFromRootToCurr);
  87.                 int rMaxFromLeaf = Solve(curr -> right, sumFromRootToCurr);
  88.  
  89.  
  90.  
  91.                 if(isleaf(curr))
  92.                 {
  93.                     curr->maxnode=curr;
  94.                 }
  95.                 if(lMaxFromLeaf>=rMaxFromLeaf && curr->left!=NULL)
  96.                 {
  97.                     curr->maxnode=curr->left->maxnode;
  98.                 }
  99.                 if(rMaxFromLeaf>lMaxFromLeaf && curr->right!=NULL)
  100.                 {
  101.                     curr->maxnode=curr->right->maxnode;
  102.                 }
  103.  
  104.                 if((sumFromRootToCurr + lMaxFromLeaf + rMaxFromLeaf)>ans)
  105.                 {
  106.                     if(curr->left!=NULL)
  107.                         X=curr->left->maxnode;
  108.                     if(curr->right!=NULL)
  109.                         Y=curr->right->maxnode;
  110.                 }
  111.  
  112.                 ans = max(ans,sumFromRootToCurr + lMaxFromLeaf + rMaxFromLeaf);
  113.  
  114.                 return (curr -> data  + max(lMaxFromLeaf,rMaxFromLeaf));        
  115.         }
  116. };
  117.  
  118. int main(){
  119.         BinaryTree bt;
  120.         bt.Construct();
  121.         //bt.PrintBT();
  122.         bt.Solve();
  123.         cout << ans << endl;
  124.         bt.printX();
  125.         bt.printY();
  126.  
  127. }
  128.  
Success #stdin #stdout 0s 2860KB
comments (?)
stdin 
Standard input is empty
stdout 
3300
X: 1000
Y: 2000
https://ideone.com/YF9qi
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!