leetcode-99. 恢复二叉搜索树_给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不

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

 输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10

二叉搜索树的中序遍历是递增的 错误交换说明在中序遍历中存在非递增的节点
因为刚好是两个节点被错误地交换 所以有两个非递增地节点 找到这两个节点 交换值即可

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        last_node = None
        maxer_node = None
        miner_node = None
        def mid_deep(root):
            nonlocal last_node
            nonlocal maxer_node
            nonlocal miner_node
            if root is None:
                return
            mid_deep(root.left)
            if last_node is not None and last_node.val > root.val:
                if maxer_node is None:
                    maxer_node = last_node
                miner_node = root
            last_node = root
            mid_deep(root.right)
        mid_deep(root)
        tmp = maxer_node.val 
        maxer_node.val = miner_node.val
        miner_node.val = tmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26