Algorithm-coding-problem/Recover Binary Search Tree.cpp at master · Stonre/Algorithm-coding-problem · 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
#include"tree.h"

    TreeNode* mistake1;
    TreeNode* mistake2;
    TreeNode* pre;
    TreeNode* post;

void cur(TreeNode* t)
{
    if (t==NULL)
        return;
    if (t->left)
        cur(t->left);
    if (pre->val>t->val)
        if (mistake1==NULL)
        {
            mistake1=pre;
            post = t;
        }
        else
            mistake2=t;
    pre=t;
    if (t->right)
        cur(t->right);

}

void recoverTree(TreeNode* root)
{
    if (root==NULL)
        return;
    TreeNode* t = root;
    while (t->left)
        t=t->left;
    pre=t;
    cur(root);
    int tmp=mistake1->val;
    if (mistake2)
    {
        mistake1->val=mistake2->val;
        mistake2->val=tmp;
    }
    else
    {
        mistake1->val=post->val;
        post->val=tmp;
    }
}

int main()
{
    ifstream f("in.txt");
    string s;
    vector<string> ss;
    while (!f.eof())
    {
        f>>s;
        ss.push_back(s);
    }
    TreeNode* t = buildtree(ss);
    recoverTree(t);
    printtree(t);
    return 0;
}