Cinte's Leetcode Record
0%

99. Recover Binary Search Tree

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

99. Recover Binary Search Tree

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        traverse(root);
        swap(first->val, second->val);
    }
private:
    TreeNode* first = nullptr;
    TreeNode* second = nullptr;
    TreeNode* pre = nullptr;
    void traverse(TreeNode* node)
    {
        if(!node)
            return;
        traverse(node->left);
        if(!first && (pre && pre->val >= node->val))
            first = pre;
        if(first && (pre && pre->val >= node->val))
            second = node;
        pre = node;
        traverse(node->right);
    }
};

S(n) : O(logn)

由inorder的顺序来看，很神奇，找规律

1
2
3
4
5
6
Nice work. However, I think it'd better to make this part more clear: the number of times that you will find prev.val >= root.val depends on whether the two nodes that get swapped are next to each other in the sequence of in-order traversal.
Let's assume this is the original in-order traversal sequence of BST: 1 2 3 4 5
If 2 and 3 get swapped, it becomes 1 3 2 4 5 and there is only one time that you will have prev.val >= root.val
If 2 and 4 get swapped, it becomes 1 4 3 2 5 and there are two times that you will have prev.val >= root.val

If during the first time when you find prev.val >= root.val, the previous node "prev" MUST be one of two nodes that get swapped. However, the current node MAY OR MAY NOT be another node that gets swapped, which will depend on whether later during in-order traversal, there is another prev.val >= root.val or not. If there is, then the current node "root" during the 2nd time of prev.val >= root.val will be the other node that gets swapped
1
2
3
4
5
How do we find these two elements? For example, we have the following tree that is printed as in order traversal:

6, 3, 4, 5, 2

We compare each node with its next one and we can find out that 6 is the first element to swap because 6 > 3 and 2 is the second element to swap because 2 < 5.

迭代实现 

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* first = nullptr, *second = nullptr, *prev = nullptr, *cur = root;
        stack<TreeNode*> s;
        while(!s.empty() || cur)
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            if(prev && prev->val > cur->val)
            {
                if(!first)
                    first = prev;
                if(first)
                    second = cur;
                if(prev != first)
                    break;
            }
            prev = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};
##### 使用morris Traversal

https://leetcode.com/problems/recover-binary-search-tree/discuss/32559/Detail-Explain-about-How-Morris-Traversal-Finds-two-Incorrect-Pointer