99. 恢复二叉搜索树

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的值即