Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Logic:
- Inorder of BST is always sorted.
- If only one node will be swapped in a BST then there is only two possibility:
- case1:
- eg Inorder: 3 25 7 8 10 15 20 5 swapped nodes(ie. 25, 5) are not adjacent
- here the current node ie. 7 is lesser than previous node,ie. 25 so make left=25,middle=7
- and again 5 is lesse than 20 so make left=5.
- if there is left,middle and right then swap(left,right);
- case 2:swapped nodes are adjacent
- eg. 3 5 8 7 10 15 20 25
- swapped node(ie. 8,7)
- using previous case left=8 and middle=7.
- no voilation or sorted order again,so no right node so,swap(left,middle)
- */
- Node *l=NULL,*m=NULL,*r=NULL,*p=NULL; //l=left,m=middle,r=right,p=previous
- void inorder(Node *root){
- if(root){
- inorder(root->left);
- if(p){
- if(root->data<p->data && !l){
- l=p;
- m=root;
- }
- else if(root->data<p->data && l){
- r=root;
- }
- }
- p=root;
- inorder(root->right);
- }
- }
- void fun(Node *root){
- if(root){
- fun(root->left);
- cout<<root->data<<" ";
- fun(root->right);
- }
- }
- class Solution {
- public:
- void correctBST( struct Node* root ){
- l=NULL;m=NULL;r=NULL;p=NULL;
- inorder(root);
- if(r){
- int temp=l->data;
- l->data=r->data;
- r->data=temp;
- }
- else{
- int temp=l->data;
- l->data=m->data;
- m->data=temp;
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement