难度: Medium
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例 1：
输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
[2, 1000] 内-231 <= Node.val <= 231 - 1进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
运行时间: 68 ms
内存: 15.3 MB
# 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.
"""
lastNode = None
n1 = None
n2 = None
def helper(root):
nonlocal lastNode, n1, n2
if root is None:
return
helper(root.left)
if lastNode is not None and lastNode.val > root.val:
if n1 is None:
n1 = lastNode
n2 = root
lastNode = root
helper(root.right)
helper(root)
n1.val, n2.val = n2.val, n1.val
这个题解使用中序遍历的方法来恢复二叉搜索树。在中序遍历二叉搜索树时，正常情况下节点值应该是递增的。如果出现节点值减小的情况，说明找到了被错误交换的两个节点。第一个错误节点是第一次发现节点值减小时的前一个节点，第二个错误节点是最后一次发现节点值减小时的当前节点。找到这两个节点后，交换它们的值即可恢复二叉搜索树。
时间复杂度: O(n)
空间复杂度: O(n)
# 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.
"""
lastNode = None # 记录中序遍历的上一个节点
n1 = None # 第一个错误节点
n2 = None # 第二个错误节点
def helper(root):
nonlocal lastNode, n1, n2
if root is None:
return
helper(root.left) # 递归遍历左子树
if lastNode is not None and lastNode.val > root.val: # 如果当前节点值小于上一个节点值
if n1 is None: # 如果是第一次发现错误，记录第一个错误节点
n1 = lastNode
n2 = root # 更新第二个错误节点为当前节点
lastNode = root # 更新上一个节点为当前节点
helper(root.right) # 递归遍历右子树
helper(root) # 中序遍历二叉搜索树
n1.val, n2.val = n2.val, n1.val # 交换两个错误节点的值以恢复二叉搜索树
在中序遍历二叉搜索树时，节点的值应该连续递增。当发现一个节点的值小于前一个节点的值时，说明发生了逆序，这是错误节点的一个标志。第一次出现逆序时，前一个节点是第一个错误节点（因为它本应比后面的值小），而当前节点是一个疑似的第二个错误节点。如果之后再次发现逆序，那么更新当前节点为第二个错误节点。这种方式有效地识别出了两个位置错误的节点，第一次逆序的前一个节点和最后一次逆序的当前节点。
在二叉搜索树中，如果只有两个节点的位置被错误交换，那么这将导致中序遍历中出现一至两处逆序。通过交换这两个节点，原本被破坏的顺序被恢复，使得所有节点重新满足二叉搜索树的性质：每个节点的左子树中的所有值都小于该节点的值，并且其右子树的所有值都大于该节点的值。这样的交换足以修复由两个节点交换引起的任何顺序错误。
当二叉搜索树退化为一条链时，树的高度等于节点数，这意味着递归方法的空间复杂度为O(n)，因为需要相应的递归调用栈空间。这种情况下，递归方法效率较低。一种更优的方法是使用迭代的中序遍历，配合显式栈来控制空间复杂度。迭代方法可以有效地管理遍历过程，减少系统调用栈的使用，从而优化在极端情况下的空间效率。
如果在中序遍历中只发现一次逆序，那么这次逆序涉及的两个节点就是错误交换的节点。在这种情况下，直接交换这两个节点的值就可以恢复树的正确性。这是因为只有一次逆序意味着只有这两个节点的位置是错误的，其余部分的顺序是正确的。