Hexo

##方法一：显式中序遍历

###思路与算法

对于二叉搜索树进行中序遍历，得到的值序列是递增有序的；对于两个错误的节点等价于在这个值序列中交换了两个值，破坏了值序列的递增性。那么序列中就会出现两个位置不满足或者一个位置不满足递增的两种情况

###解决方案

• 中序递归遍历整个树，当 pre 节点值大于当前节点，记录这两个节点。
• 判断逆序对节点数是2个还是4个，如果是2两个，交换即可，如果是4个，则交换第1个和第4个。

代码

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def _inorder(root):
            if not root: return
            # 遍历左子树
            _inorder(root.left)
            
            nonlocal pre, nodes
            if pre and pre.val > root.val:  # 记录当前的逆序对
                nodes.append(pre)
                nodes.append(root)
            pre = root
            # 遍历右子树
            _inorder(root.right)

        pre = None
        nodes = []
        _inorder(root)
        if len(nodes) == 2:
            i, j = 0, 1
        elif len(nodes) == 4:
            i, j = 0, 3
        else:
            return
        nodes[i].val, nodes[j].val = nodes[j].val, nodes[i].val
        return

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦