【Leetcode】【python】Recover Binary Search Tree 恢复二叉搜索树

题目大意

一颗二叉查找树中的某两个节点被错误的交换了，需要恢复成原来的正确的二叉查找树。

挑战：是要求空间复杂度为常数空间。空间复杂度为O(N)是常规解法。

解题思路

来自：博客

算法一：
思路很简单，一颗二叉查找树的中序遍历应该是升序的，而两个节点被交换了，那么对这个错误的二叉查找树中序遍历，肯定不是升序的。那我们只需把顺序恢复过来然后进行重新赋值就可以了。（可针对任意个数目的节点错乱的情况）

算法二：
该算法依然是O(n)空间复杂度，其博客说法有误。
使用了一个prev指针。例如一颗被破坏的二叉查找树如下：

        　　　　　　4

    　　　　　　　/     \

　　            2      6

            /   \    /   \

           1    5   3      7

很明显3和5颠倒了。那么在中序遍历时：当碰到第一个逆序时：为5->4，那么将n1指向5，n2指向4，注意，此时n1已经确定下来了。然后prev和root一直向后遍历，直到碰到第二个逆序时：4->3，此时将n2指向3，那么n1和n2都已经确定，只需要交换节点的值即可。prev指针用来比较中序遍历中相邻两个值的大小关系。

算法三：
O(1)空间复杂度解法网上有很多，比较难理解，有空深入，这里列举我看到的一种
这道题的真正符合要求的解法应该用的Morris遍历，这是一种非递归且不使用栈，空间复杂度为O(1)的遍历方法，可参见我之前的博客Binary Tree Inorder Traversal 二叉树的中序遍历，在其基础上做些修改，加入first, second和parent指针，来比较当前节点值和中序遍历的前一节点值的大小，跟上面递归算法的思路相似。

代码

算法一

思路太明确但是太笨，在此不贴代码，我认为可以忽略。

算法二

class Solution(object):
    def FindTwoNodes(self, root):
        if root:
            self.FindTwoNodes(root.left)
            if self.prev and self.prev.val > root.val:
                self.n2 = root
                if not self.n1: 
                    self.n1 = self.prev
            self.prev = root
            self.FindTwoNodes(root.right)

    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.n1 = self.n2 = None
        self.prev = None
        self.FindTwoNodes(root)
        self.n1.val, self.n2.val = self.n2.val, self.n1.val

算法三（Java）

class Solution {
public:
    void recoverTree(TreeNode *root) {
        TreeNode *first = NULL, *second = NULL, *parent = NULL;
        TreeNode *cur, *pre;
        cur = root;
        while (cur) {
            if (!cur->left) {
                if (parent && parent->val > cur->val) {
                    if (!first) first = parent;
                    second = cur;
                }
                parent = cur;
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    if (parent->val > cur->val) {
                        if (!first) first = parent;
                        second = cur;
                    }
                    parent = cur;
                    cur = cur->right;
                }
            }
        }
        if (first && second) swap(first->val, second->val);
    }
};

总结

这道题暂时先学会算法二足够，之后再深入。