99. 恢复二叉搜索树

题目描述

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

思路

和 98. 验证二叉搜索树一样，中序遍历正好可以按递增的顺序对比节点，这样只需要记录有问题的节点即可。

由于恰好只有两个值被交换了，那么一定有一个是比它前后的数大的，也有一个比它前后的数小的。

那么中序遍历一次，一定能找到比他前后数字都大的，但是可能有多个比它前后数字都小的，此时我们取最后一个。

最终代码：

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        x = None
        y = None
        pre = None
        def dfs(node):
            nonlocal pre, x, y
            if node == None:
                return
            dfs(node.left)
            if pre and pre.val > node.val:
                if not x:
                    x = pre
                # 记录最后一个需要调换的位置
                y = node
            pre = node
            dfs(node.right)
 
        dfs(root)
        x.val, y.val = y.val, x.val

想得太多