#中序遍历，寻找插值位置并交换
# 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: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        #记录中序遍历的值
        nums = []
        self.inorder(root, nums)
        print(nums)
        x,y = self.swappos(nums)
        self.swap(root,2,x,y)

        #找到替换值的位置
    def inorder(self, root, nums):
        if root:
            self.inorder(root.left,nums)
            nums.append(root.val)
            self.inorder(root.right,nums)

    def swappos(self, nums):
        n = len(nums)
        index1 = -1
        index2 = -1
        for i in range(n-1):
            if nums[i+1] < nums[i]:
                index1 = i+1
                if index2 == -1:
                    index2 = i
                else:
                    break
        x,y = nums[index2], nums[index1]
        return [x,y]
    def swap(self, root, count, num1, num2):
        if root:
            if root.val == num1 or root.val == num2:
                root.val = num2 if root.val == num1 else num1
                count -= 1
                if count == 0:
                    return
            self.swap(root.left, count, num1, num2)
            self.swap(root.right, count, num1, num2)

#边中序遍历，边判断

# 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):
        stack = []
        x, y = None, None
        prev = None
        #迭代形式的中序遍历：借助栈
        while stack or root:
            #遍历左子树
            while root:
                stack.append(root)
                root = root.left
            #左子树遍历完，root为null
            root = stack.pop()

            if prev and root.val < prev.val:
                x = root
                if y == None:
                    y = prev
                else:
                    break
            #这个root判断完，将其赋予prev
            prev = root
            root = root.right
        self.swap(x,y)
    def swap(self,x,y):
        tmp = y.val
        y.val = x.val
        x.val = tmp

 

#moriss遍历
class Solution:
    def recoverTree(self, root):
        x, y, pred, predecessor = None, None, None, None

        while root:
            if root.left:
                predecessor = root.left
                while predecessor.right and predecessor.right != root:
                    predecessor = predecessor.right
                if predecessor.right == None:
                    predecessor.right = root
                    root = root.left

                else:
                    predecessor.right = None
                    root = root.right
            else:
                root = root.right

 

# 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):
        x, y, pred, predecessor = None, None, None, None

        while root:
            if root.left:
                predecessor = root.left
                while predecessor.right and predecessor.right != root:
                    predecessor = predecessor.right
                if predecessor.right == None:
                    predecessor.right = root
                    root = root.left

                else:
                    if pred and root.val < pred.val:
                        #y为后面那个值
                        y = root
                        if not x:
                            x = pred
                    pred = root

                    predecessor.right = None
                    root = root.right
            else:
                if pred and root.val < pred.val:
                    y = root
                    if not x:
                        x = pred
                pred = root
                root = root.right
        x.val,y.val = y.val,x.val