#中序遍历，寻找插值位置并交换
# 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 = -1index2 = -1for i in range(n-1):if nums[i+1] < nums[i]:index1 = i+1if index2 == -1:index2 = ielse:breakx,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 num1count -= 1if count == 0:returnself.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, Noneprev = None#迭代形式的中序遍历：借助栈while stack or root:#遍历左子树while root:stack.append(root)root = root.left#左子树遍历完，root为nullroot = stack.pop()if prev and root.val < prev.val:x = rootif y == None:y = prevelse:break#这个root判断完，将其赋予prevprev = rootroot = root.rightself.swap(x,y)def swap(self,x,y):tmp = y.valy.val = x.valx.val = tmp

 

#moriss遍历
class Solution:def recoverTree(self, root):x, y, pred, predecessor = None, None, None, Nonewhile root:if root.left:predecessor = root.leftwhile predecessor.right and predecessor.right != root:predecessor = predecessor.rightif predecessor.right == None:predecessor.right = rootroot = root.leftelse:predecessor.right = Noneroot = root.rightelse: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, Nonewhile root:if root.left:predecessor = root.leftwhile predecessor.right and predecessor.right != root:predecessor = predecessor.rightif predecessor.right == None:predecessor.right = rootroot = root.leftelse:if pred and root.val < pred.val:#y为后面那个值y = rootif not x:x = predpred = rootpredecessor.right = Noneroot = root.rightelse:if pred and root.val < pred.val:y = rootif not x:x = predpred = rootroot = root.rightx.val,y.val = y.val,x.val