fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<limits.h>
  4. #include<stdbool.h>
  5.  
  6.   typedef struct node {
  7.     int val;
  8.     struct node *next;
  9.    } node;
  10.  
  11.    typedef struct Treenode {
  12.         int val;
  13.         struct Treenode *left;
  14.         struct Treenode *right;
  15.     } Treenode;
  16.  
  17.    Treenode *createnode(){
  18.         Treenode *totree = (Treenode*)malloc(sizeof(Treenode));
  19.         totree->left=NULL;
  20.         totree->right=NULL;
  21.         return totree;
  22.    }
  23.  
  24.    void InOrder(Treenode *root){
  25.         if(!root) return;
  26.         InOrder(root->left);
  27.         printf("%d ",root->val);
  28.         InOrder(root->right);
  29.    }
  30.  
  31.    void preOrder(Treenode *root){
  32.         if(!root) return;
  33.         printf("%d ",root->val);
  34.         preOrder(root->left);
  35.         preOrder(root->right);
  36.    }
  37.  
  38.    void PostOrder(Treenode *root){
  39.         if(!root) return;
  40.         PostOrder(root->left);
  41.         PostOrder(root->right);
  42.         printf("%d ",root->val);
  43.    }
  44.  
  45.    Treenode *arrayTotree(int *a, int size ,int i){
  46.         if(i>=size) return NULL;
  47.         Treenode *root=createnode();
  48.         root->val=a[i];
  49.         root->left=arrayTotree(a,size,2*i+1);
  50.         root->right=arrayTotree(a,size,2*i+2);
  51.         return root;
  52.    }
  53.  
  54.    bool isMirror_help(Treenode *p,Treenode *q){
  55.         if(!p && !q) return true;
  56.         else if(!p || !q) return false;
  57.         if(p->val != q->val) return false;
  58.         return isMirror_help(p->left,q->right) && isMirror_help(p->right,q->left);
  59.    }
  60.  
  61.    bool isMirror(Treenode *root){
  62.         if(!root) return true;
  63.         return isMirror_help(root->left,root->right);
  64.    }
  65.  
  66.  
  67.     int treeHeight(Treenode *root){
  68.         if(!root) return 0;
  69.         int con1=treeHeight(root->left);
  70.         int con2=treeHeight(root->right);
  71.         return 1+((con1>con2)?con1:con2);
  72.     }  
  73.  
  74.     Treenode *LCA(Treenode *root,int x,int y){
  75.         if(!root) return NULL;
  76.         if(root->val==x || root->val==y) return root;
  77.         Treenode *node1 = LCA(root->left,x,y);
  78.         Treenode *node2 = LCA(root->right,x,y);
  79.         if(node1 && node2) return root;
  80.         if(!node1) return node2;
  81.         return node1;                                                                                   
  82.     }
  83.  
  84.     int size_BST(Treenode *root){
  85.         if(!root) return 0;
  86.         return 1+size_BST(root->left)+size_BST(root->right);
  87.     }
  88.  
  89.     Treenode *search_BST(Treenode *root , int key){
  90.         if(!root) return NULL;
  91.         if(root->val>key)
  92.           return search_BST(root->left,key);
  93.         if(root->val<key) 
  94.           return search_BST(root->right,key);
  95.         return root;    
  96.     }
  97.  
  98.     bool isBST_help(Treenode *root,int min,int max){
  99.         if(!root) return true;
  100.         if(root->left && root->left->val>=root->val) return false;
  101.         if(root->right && root->right->val<=root->val) return false;
  102.         if(root->val<=min || root->val>=max) return false;
  103.         return isBST_help(root->left,min,root->val) && isBST_help(root->right,root->val,max);
  104.     }
  105.  
  106.     bool isBST(Treenode *root){
  107.         return isBST_help(root,INT_MIN,INT_MAX);
  108.     }
  109.  
  110.    int main(){
  111.  
  112.     Treenode *root = createnode();
  113.     root->val = 8;
  114.  
  115.     Treenode *left1 = createnode();
  116.     left1->val = 4;
  117.     root->left = left1;
  118.  
  119.     Treenode *right1 = createnode();
  120.     right1->val = 12;
  121.     root->right = right1;
  122.  
  123.     Treenode *left2 = createnode();
  124.     left2->val = 2;
  125.     left1->left = left2;
  126.  
  127.     Treenode *right2 = createnode();
  128.     right2->val = 6;
  129.     left1->right = right2;
  130.  
  131.     Treenode *left3 = createnode();
  132.     left3->val = 1;
  133.     left2->left = left3;
  134.  
  135.     Treenode *right3 = createnode();
  136.     right3->val = 3;
  137.     left2->right = right3;
  138.  
  139.     Treenode *left4 = createnode();
  140.     left4->val = 5;
  141.     right2->left = left4;
  142.  
  143.     Treenode *right4 = createnode();
  144.     right4->val = 7;
  145.     right2->right = right4;
  146.  
  147.     Treenode *right5 = createnode();
  148.     right5->val = 10;
  149.     right1->left = right5;
  150.  
  151.     Treenode *right6 = createnode();
  152.     right6->val = 14;
  153.     right1->right = right6;
  154.  
  155.     Treenode *left5 = createnode();
  156.     left5->val = 9;
  157.     right5->left = left5;
  158.  
  159.     Treenode *right7 = createnode();
  160.     right7->val = 11;
  161.     right5->right = right7;
  162.  
  163.     Treenode *left6 = createnode();
  164.     left6->val = 13;
  165.     right6->left = left6;
  166.  
  167.     Treenode *right8 = createnode();
  168.     right8->val = 15;
  169.     right6->right = right8;
  170.  
  171.     InOrder(root);
  172.     printf("\n");
  173.     printf("%d\n",size_BST(root));
  174.     if(isBST(root)) printf("NICE\n");
  175.  
  176.    }
  177.  
  178.  
  179.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
15
NICE
https://ideone.com/mMqjna
language:
C++ (gcc 8.3)
created:
8 hours 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!