data-structures-and-algorithms/Recover_BST.cpp at main · Open-code-source/data-structures-and-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
using namespace  std;


class Node{
public:
	int data;
	Node *left,*right;

	Node(int val){
		data=val;
		left=right=NULL;
	}
};

void swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

void calcPoint(Node *root,Node **first,Node **mid ,Node **last,Node **prev){
	if(root==NULL){
		return;
	}

	calcPoint(root->left,first,mid,last,prev);

	if(*prev && root->data<(*prev)->data){

		if(!*first){
			*first=*prev;
			*mid=root;
		}else{
			*last=root;

		}
	}

	*prev=root;
	calcPoint(root->right,first,mid,last,prev);


}

void restoreBST(Node* root){
	if(root==NULL){
		return;
	}

	Node *first,*mid,*last,*prev;
	first=NULL;
	mid=NULL;
	last=NULL;
	prev=NULL;

	calcPoint(root,&first,&mid,&last,&prev);

	if(first && last){
		swap(&(first->data),&(last->data));
	}
	else if(first && mid){
		swap(&(first->data),&(last->data));
	}


}

void inorder(Node *root){
	if(root==NULL){
		return;

	}

	inorder(root->left);
	cout<<root->data<<" ";
	inorder(root->right);
}

int main(){


	Node *root=new Node(6);
	root->left=new Node(9);
	root->right=new Node(3);
	root->left->left=new Node(1);
	root->left->right=new Node(4);

	root->right->right=new Node(13);


	inorder(root);
cout<<endl;
	restoreBST(root);

	inorder(root);
	cout<<endl;

	return 0;
}