https://leetcode.com/problems/recover-binary-search-tree/
空间解法！

个人解法

  1. class Solution:
  2.     def recoverTree(self, root: Optional[TreeNode]) -> None:
  3.         """
  4.         Do not return anything, modify root in-place instead.
  5.         """
  6.         self.leftMax = -math.inf
  7.         self.swapped = []
  8.         def inorder(root):
  9.             if not root:
  10.                 return
  11.             inorder(root.left)
  12.             if root.val < self.leftMax:
  13.                 if not self.swapped:
  14.                     self.swapped = [self.leftMax, root.val]
  15.                 else:
  16.                     self.swapped[1] = root.val
  17.             self.leftMax = root.val
  18.             inorder(root.right)
  20.         inorder(root)
  22.         def recover(root, swapped):
  23.             if not root:
  24.                 return
  25.             if root.val == swapped[0]:
  26.                 root.val = swapped[1]
  27.             elif root.val == swapped[1]:
  28.                 root.val = swapped[0]
  30.             recover(root.left, swapped)
  31.             recover(root.right, swapped)
  33.         recover(root, self.swapped)

题目分析

比较直观的方式是，根据BST的性质，中序遍历应该是有序的，只要中序遍历一遍，存下来，跟有序的对比一下就好。

  1. class Solution:
  2.     def recoverTree(self, root: Optional[TreeNode]) -> None:
  3.         """
  4.         Do not return anything, modify root in-place instead.
  5.         """
  6.         def inorder(root):
  7.             if not root:
  8.                 return []
  9.             return inorder(root.left) + [root.val] + inorder(root.right)
  11.         a = inorder(root)
  12.         b = sorted(a)
  13.         for i in range(len(a)):
  14.             if a[i] != b[i]:
  15.                 swapped = [a[i], b[i]]
  16.                 break
  18.         def recover(root, swapped):
  19.             if not root:
  20.                 return
  21.             if root.val == swapped[0]:
  22.                 root.val = swapped[1]
  23.             elif root.val == swapped[1]:
  24.                 root.val = swapped[0]
  26.             recover(root.left, swapped)
  27.             recover(root.right, swapped)
  29.         recover(root, swapped)

这样的空间复杂度是O(n)，如果用固定空间，只能在中序遍历的过程中检测交换的节点了。
还是把握交换后的性质，中序遍历时不断更新遍历到的最大值，如果发现当前值比最大值小，那么必然存在问题，记录即可。