https://leetcode-cn.com/problems/recover-binary-search-tree/
解法一：中序
先中序遍历得到结点值列表，然后排序，再中序遍历一次，将排序后的值依次填入即可。空间复杂度O（n）
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
vals = []
def traval(root): #函数，中序遍历记录所有结点
if not root:
return
traval(root.left)
vals.append(root.val)
traval(root.right)
traval(root)
vals.sort() #值排序
def fill(root): #函数，第二次遍历，依次填入新值
if not root:
return
fill(root.left)
root.val = vals[0]
vals.pop(0)
fill(root.right)
fill(root)
解法二：中序，空间复杂度O（1）
假设现在有一个乱掉的二叉搜索树[1,2,5,4,3,6,7] 很明显3和5颠倒了。那么在中序遍历时：当碰到第一个逆序时：为5->4，那么将n1指向5，n2指向4， 注意，此时n1已经确定下来了。然后prev和root一直向后遍历，直到碰到第二个逆序时：4->3，此时将n2指向3， 那么n1和n2都已经确定，只需要交换节点的值即可。prev指针用来比较中序遍历中相邻两个值的大小关系。
作者：Young1 链接：https://leetcode-cn.com/problems/two-sum/solution/python-by-young1-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
[1,6,3,4,5,2,7]同上，也是有两段颠倒:[6,3],[5,2]
[1,3,2,4]只有一段颠倒，一次判断就能确定n1，n2
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.n1, self.n2 = None, None #记录要交换的两节点
self.prev = None #记录上一个结点
def helper(root):
if not root:
return
helper(root.left)
if self.prev and self.prev.val > root.val:
if not self.n1:
self.n1 = self.prev
self.n2 = root
self.prev = root
helper(root.right)
helper(root)
self.n1.val, self.n2.val = self.n2.val, self.n1.val #交换n1，n2的值即
