99. 恢复二叉搜索树 [hard]

https://leetcode-cn.com/problems/recover-binary-search-tree/

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

通过次数21,272 | 提交次数36,928

Second Try

2020-09-02

时隔多日重做，看到困难题还是有点畏难而退，还好依然想出了中序排序来处理。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        # 搞出中序遍历，然后找到两个节点进行替换
        # 只修改val不知是否可以，如果要修改node本身那就难了
        def dfs_inorder(node, rv):
            if not node:
                return 
            if node.left:
                dfs_inorder(node.left, rv)
            rv.append(node)
            if node.right:
                dfs_inorder(node.right, rv)
        
        rv = []
        dfs_inorder(root, rv)
        srv = sorted(rv, key=lambda x: x.val)
        swich_pair = []
        for i in range(len(rv)):
            if rv[i] != srv[i]:
                swich_pair.append(i)
        i, j = swich_pair
        rv[i].val, rv[j].val = rv[j].val, rv[i].val 

First Try

2020-07-17

用中序遍历来辅助纠错，事情变得简单了起来，任意n个放错位置也能被识别。

理解错了好几次，其一是不需要返回，只是原地修改；其二是原来两个交换的点不一定是临近点，可以是任意点。

原地修改那么说明只是修改val,毕竟不允许修改val，在root也被调换的话就没法处理了。其次可以是任意点，说明需要遍历所有点出来后才知道了。

但是还是不知道怎么写空间非O(n)的算法，不用中序遍历来辅助，感觉很难办了啊。

看了题解，O(1)空间的解法只能用morris遍历了，没时间不想去深究了。

其次对一个有序递增序列里两个元素被交换的问题，题解用了一种O(n)的一次性扫描方法。遇到的第一个n[i+1] < n[i]的点，i点是错位点；遇到第二个n[i+1] < n[i]的点，i + 1是错位点。写个有序递增序列，调换任意两个元素，看一下就明白了。然后将这两个点进行交换即可，操作过程中需要判断这是第几次遇到了。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 只是交换了两个节点而已吗
        # 而且modify root in place,那就代表只是交换val而已
        # 两个节点可能在任意位置，我还以为是就近节点。。。
        # 还是用中序遍历吧
        if not root:
            return root 

        seq = []

        def dfs_inorder(root, seq):
            if not root:
                return 
            dfs_inorder(root.left, seq)
            seq.append(root)
            dfs_inorder(root.right, seq)
        
        dfs_inorder(root, seq)

        nseq = sorted(seq, key=lambda x: x.val)

        sw = []
        for i in range(len(seq)):
            if seq[i] != nseq[i]:
                sw.append(i)
        if len(sw) != 2:  # 照题意不会发生，所以随意写了一个
            return 
        i, j = sw
        seq[i].val, seq[j].val = seq[j].val, seq[i].val
        

执行用时：60 ms, 在所有 Python 提交中击败了78.82%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了100.00%的用户

failed try

以为只是交换两个临近的节点，而且只修改关联关系而不修改val，写了个不错的递归表达式，结果gg了。

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 只是交换了两个节点而已吗

        if not root:
            return root 

        if root.left: 
            left = root.left
            right = root.right 
            if left.val > root.val:
                 root.left = left.left 
                 root.right = left.right
                 left.left = root 
                 left.right = right 
                 print('catch', left)
                 return left  
            else:
                root.left = self.recoverTree(root.left)
        if root.right:
            right = root.right
            left = root.left 
            if right.val < root.val:
                root.left = right.left 
                root.right = right.right 
                right.right = root
                right.left = left 
                return right
            else:
                root.right = self.recoverTree(root.right)
        
        return root 