fork download
copy 
  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.  
  11.         Node(int val, Node* l = NULL, Node* r = NULL){
  12.                 data = val;
  13.                 left = l;
  14.                 right = r;
  15.         }
  16. }*X,*Y;
  17.  
  18. class BinaryTree{
  19.         Node* Root;
  20.  
  21.         public:
  22.         BinaryTree(){
  23.                 Root = NULL;
  24.         }
  25.         void Construct(){
  26.                 Node* d = new Node(100);
  27.                 Node* e = new Node(300);
  28.                 //Node* f = new Node(25,l,m);
  29.                 Node* g = new Node(10);
  30.                 Node* b = new Node(5,d,e);
  31.                 Node* c = new Node(8,NULL,g);
  32.                 Node* a = new Node(1,b,c);
  33.                 Root = a;
  34.         }
  35.  
  36.         void PrintInOrder(Node *temp){
  37.                 if(temp != NULL){
  38.                         PrintInOrder(temp -> left);
  39.                         cout << temp -> data << endl;
  40.                         PrintInOrder(temp -> right);            
  41.                 }
  42.         }
  43.  
  44.         void PrintBT(){
  45.                 PrintInOrder(Root);
  46.         }
  47.  
  48.         void Solve(){
  49.         	Node* Lmax;
  50.                 Solve(Root,0, Lmax);
  51.         }
  52.  
  53.         int Solve(Node *curr, int sumFromParent, Node* &L){
  54.                 if(curr == NULL){ 
  55.          		L = NULL;
  56.                 	return 0;
  57.                 }
  58.  
  59.                 if(curr -> left == NULL && curr -> right == NULL){
  60.                 	L = curr;
  61.                 	return curr -> data;
  62.                 }
  63.  
  64.                 Node* lx;
  65.                 Node* ry;
  66.  
  67.                 int sumFromRootToCurr = sumFromParent + curr -> data;
  68.                 int lMaxFromLeaf = Solve(curr -> left, sumFromRootToCurr, lx);
  69.                 int rMaxFromLeaf = Solve(curr -> right, sumFromRootToCurr, ry);
  70.  
  71.                 (lMaxFromLeaf > rMaxFromLeaf) ? (L = lx) : (L = ry);
  72.  
  73.                 if(ans < sumFromRootToCurr + lMaxFromLeaf + rMaxFromLeaf){
  74.                 	ans = sumFromRootToCurr + lMaxFromLeaf + rMaxFromLeaf;
  75.                 	X = lx;
  76.                 	Y = ry;
  77.                 }
  78.  
  79.                 return (curr -> data  + max(lMaxFromLeaf,rMaxFromLeaf));        
  80.         }
  81. };
  82.  
  83. int main(){
  84.         BinaryTree bt;
  85.         bt.Construct();
  86.         //bt.PrintBT();
  87.         bt.Solve();
  88.         cout << "X : " << X -> data << endl;
  89.         cout << "Y : " << Y -> data << endl;
  90.         cout << "Required Value : " << ans << endl;
  91. } 
  92.  
Success #stdin #stdout 0s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
X : 100
Y : 300
Required Value : 406
https://ideone.com/1ZtIq
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!