99. 恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。

示例 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

思路：

因为只有一对结点是错误的，所以中序遍历的结果只有两种情况。

• 第一种情况：结果中如果有一个降序对，说明该两个node需交换；

• 第二种情况：有两个降序对，而且这两个降序对是相连的，且第一个降序对的后者是第二个降序对的前者，即两个降序对只有三个节点，所以说明第一对的前一个node和第二对的后一个node需要交换。

  代码

  # 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 __init__(self):
        self.res = []
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.mid(root)
        node1, node2 = None, None
        for i in range(len(self.res)-1):
            if self.res[i].val > self.res[i+1].val and node1 == None:
                node1 = self.res[i]
                node2 = self.res[i+1]
            elif self.res[i].val > self.res[i+1].val and node1 != None:
                node2 = self.res[i+1]
        node1.val, node2.val = node2.val, node1.val
    def mid(self, root):
        if root != None :
            self.mid(root.left)
            self.res.append(root)
            self.mid(root.right)