LeetCode笔记（6）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?

首先想想这道题所说的O(n) space。既然是一棵BST, 那么inorder遍历下来必然是一个有序数组（假设递增）。递增数组中有两个数字位置颠倒，需要找出来并恢复。那就是说，有两个数字的位置发生了错误。对第一个错误来说，很明显：它会大于之后的一个数。而对于第二个错误，有两种可能：紧跟第一个错误（连续的两个数字对调位置） 或者 在之后其他位置（两个不连续的数字位置对调）。对于这两种情况来说，有一个共性：第二个错误的数字都会小于自己之前的一位。

根据这一道理，O(n) space的算法很容易得到，code就不再写了。

而对于constant space，可以中序遍历的同时用两个指针来分别记录两个错误，为了比较，需要在遍历时记录一个pre指针，得到代码如下：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode * pre;
    TreeNode * first;
    TreeNode * second;
public:
    void inorder(TreeNode * root)
    {
        if (!root)
            return;

        inorder(root->left);
        if (pre && pre->val > root->val )
        {
            if (first == NULL)
                first = pre;
            second = root;
        }
        pre = root;
        inorder(root->right);
    }

    void recoverTree(TreeNode *root) {
        pre = NULL;
        first = NULL;
        second = NULL;
        inorder(root);
        if (first && second)
        {
            int tmp = first->val;
            first->val = second->val;
            second->val = tmp;
        }
    }
};

也有说这种算法不是O(1) space的，因为用了递归，函数调用栈空间最少O(log(n))。对此我表示认同，但是为了得到绝对的O(1)算法过于复杂，在此略去，可以参见这里。

经验教训：

• 做这道题之前刚做了Validate Binary Search Tree，用同样的思路想了很久之后终于放弃，发现直接从头思考更直接。所以说，长的像的题目解法也可能大不同，施主不要过于执念0_0||
• 找两个错误的位置比较并不是很直观。最好的方法还是举例分析
• 开始就思考O(1)有点困难，tree和比较什么混在一起。既然有提示，还是一步步来，问题各部分分别思考清楚。步子太大，容易扯着蛋。