[LeetCode 99] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Diffculty
Hard

Similar Problems

Analysis

一看到 BST 的问题，第一反应就应该是 inorder traversal。

利用 O(n) 的空间复杂度的话比较简单，用一个数组存储 inorder traversal 的结果，排个序，再赋值回去就好了。这个方法对于有任意 N 个元素位置不对的BST也可行。

这里只有两个 node 位置错了，因此可以只要找到这两个节点，用 O(logn) 空间复杂度的递归就可以找到。维护三个指针，pre, first 和 second。pre 用来存储 inorder traversal 的前一个节点，用以和当前节点进行比较来决定当前节点是否违反 BST 的性质。first 和 second 存储两个放错了的 Node 。

比如这个正确的 BST：

1 2 3 4 5 6 7

交换一下 1 和 4 得到：

4 2 3 1 5 6 7

因为只有两个 Node 放错了，因此在遍历中序遍历所生成的数组序列时，第一个出现逆序 (a1, a2) pair 中的 a1 作为第一个放错的节点，第二个出现逆序的 (b1, b2) pair 中的 b2 作为放错的节点。

遍历： 第一次，pre = 4，root = 2，出现了逆序，说明 4 是放错了的 Node ，因此，令 first = pre，也即 first = 4 。 第二次 pre = 3, root = 1 又出现了逆序，说明 1 是放错了的 Node，因此，令 second = root，也即 second = 1。

这样就找到了两个节点，交换他们的值就行了。

Solutions

class Solution {
public:
    void recoverTree(TreeNode *root) {
        inorder(root);
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
    void inorder(TreeNode *root) {  
       if(root == nullptr) return;

       // 左
       inorder(root->left);

       // 中     
       if(pre == nullptr) {
           pre = root;
       } else {
           if(pre->val > root->val) {  // 出现逆序
               if(first == nullptr)
                   first = pre;
               second = root;
           }
           pre = root;
       }

       // 右
       inorder(root->right);
    }

    Solution() : pre (nullptr), first (nullptr), second (nullptr){}

private:
    TreeNode *pre;
    TreeNode *first;
    TreeNode *second;
};