[Leetcode][python]Recover Binary Search Tree/恢复二叉搜索树

本是古典何须时尚 2022-06-11 07:10 167阅读 0赞

## 题目大意 ##

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

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

## 解题思路 ##

来自：[博客][Link 1]

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

算法二：  
**该算法依然是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

### 算法三（C++） ###

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);
        }
    };

## 总结 ##

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

[Link 1]: http://www.cnblogs.com/zuoyuan/p/3746594.html