fork download
copy 
  1.  
  2. #include<iostream>
  3. #include<queue>
  4. using namespace std;
  5. class node{
  6. public:
  7.     node *left;
  8.     node *right;
  9.     int data;
  10.     node(int d)
  11.     {
  12.         data = d;
  13.         left = NULL;
  14.         right = NULL;
  15.     }
  16. };
  17.  
  18. node *buildTree(){
  19.     int d;
  20.     cin>>d;
  21.     if(d == -1){
  22.         return NULL;
  23.     }
  24.     node *root = new node(d);
  25.     root->left = buildTree();
  26.     root->right = buildTree();
  27.     return root;
  28. }
  29. void print_pre(node *root){
  30.     if(root == NULL){
  31.         return;
  32.     }
  33.     cout<<root->data<<" ";
  34.     print_pre(root->left);
  35.     print_pre(root->right);
  36. }
  37. void print_in(node *root){
  38.     if(root == NULL){
  39.         return;
  40.     }
  41.     print_in(root->left);
  42.     cout<<root->data<<" ";
  43.     print_in(root->right);
  44. }
  45. void print_post(node *root){
  46.     if(root == NULL){
  47.         return;
  48.     }
  49.     print_post(root->left);
  50.     print_post(root->right);
  51.     cout<<root->data<<" ";
  52. }
  53. int height(node *root){
  54.     if(root==NULL){
  55.         return 0;
  56.     }
  57.     int lh = height(root->left);
  58.     int rh = height(root->right);
  59.     return max(lh,rh)+1;
  60. }
  61. void Printkthlevel(node *root ,int k){
  62.     if(root==NULL){
  63.         return;
  64.     }
  65.     if(k==1){
  66.         cout<<root->data<<" ";
  67.         return;
  68.     }
  69.     Printkthlevel(root->left,k-1);
  70.     Printkthlevel(root->right,k-1);
  71. }
  72. void printAllLevels(node *root){
  73.     int h = height(root);
  74.     for(int i=1;i<=h;i++){
  75.         Printkthlevel(root,i);
  76.          cout<<endl;
  77.     }
  78.     return;
  79. }
  80. void bfs(node *root){
  81.     queue<node*>q;
  82.     q.push(root);
  83.     //for printing each level in next line
  84.     q.push(NULL);
  85.     while(!q.empty()){
  86.         node *f = q.front();
  87.  
  88.         //for printing each level in next line
  89.         if(f==NULL){
  90.             cout<<endl;
  91.             q.pop();
  92.             if(!q.empty()){
  93.                 q.push(NULL);
  94.             }
  95.         }
  96.         else{
  97.             cout<<f->data<<" ";
  98.             q.pop();
  99.             if(f->left){
  100.                 q.push(f->left);
  101.             }
  102.             if(f->right){
  103.                 q.push(f->right);
  104.             }
  105.         }
  106.  
  107.     }
  108.     return;
  109. }
  110. int Count(node*root){
  111.     if(root == NULL){
  112.         return 0;
  113.     }
  114.     return 1+Count(root->left)+Count(root->right);
  115. }
  116. int sumAllNodes(node *root){
  117.     int sum=0;
  118.     if (root==NULL){
  119.         return 0;
  120.     }
  121.     sum += (root->data+sumAllNodes(root->left)+sumAllNodes(root->right));
  122.     return sum;
  123.  
  124. }
  125. int diameter(node *root){
  126.     if(root == NULL){
  127.         return 0;
  128.     }
  129.     int h1 = height(root->left);
  130.     int h2 = height(root->right);
  131.     int case1 = h1+h2;
  132.     int case2 = diameter(root->left);
  133.     int case3 = diameter(root->right);
  134.     return max(case1,max(case2,case3));
  135. }
  136. class Pair {
  137. public:
  138.     int height;
  139.     int diameter;
  140. };
  141. Pair diameterEfficient(node *root){
  142.     //p.first = height, p.second = diameter
  143.     Pair p,left,right;
  144.  
  145.     if(root==NULL){
  146.         p.height = p.diameter = 0;
  147.         return p;
  148.     }
  149.     left = diameterEfficient(root->left);
  150.     right = diameterEfficient(root->right);
  151.     p.height = 1+ max(left.height,right.height);
  152.     p.diameter = max(left.height+right.height,max(left.diameter,right.diameter));
  153.     return p;
  154. }
  155. int replaceSum(node *root){
  156.     if(root == NULL){
  157.         return 0;
  158.     }
  159.     if(root->left==NULL && root->right==NULL){
  160.         return root->data;
  161.     }
  162.     int leftSum = replaceSum(root->left);
  163.     int rightSum = replaceSum(root->right);
  164.  
  165.     int temp = root->data;
  166.     root->data = leftSum+rightSum;
  167.     return temp+root->data;
  168.  
  169. }
  170. int main(){
  171.     node *root = buildTree();
  172.     /*print_pre(root);
  173.     cout<<endl;
  174.     print_in(root);
  175.     cout<<endl;
  176.     print_post(root);*/
  177.     //cout<<height(root)<<endl;
  178.     //Printkthlevel(root,3);
  179.     //printAllLevels(root);
  180.     bfs(root);
  181.     cout<<endl;
  182.     /*int c = Count(root);
  183.     cout<<c<<endl;
  184.     int s = sumAllNodes(root);
  185.     cout<<s;
  186.     cout<<endl;
  187.     int d = diameter(root);
  188.     cout<<d<<endl;
  189.     Pair de = diameterEfficient(root);
  190.     cout<<de.height<<" "<<de.diameter<<endl;*/
  191.      replaceSum(root);
  192.      bfs(root);
  193. return 0;}
  194.  
  195.  
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
3 4 -1 6 -1 -1 5 1 -1 -1 -1
stdout
copy 
3 
4 5 
6 1 

16 
6 1 
6 1
https://ideone.com/KvKZAQ
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!