本文共 946 字，大约阅读时间需要 3 分钟。
BST ==》中序遍历是有序的
如果被误操作： BST ==》中序遍历一定不是有序的 找到就好啦～ 第一个乱序的数字是pre，第二个乱序的数字是root，用两个指针分别保存，然后交换值即可，不需要把树完全遍历完。时间复杂度 O(n)
O(1) # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def recoverTree(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ self.n1 = self.n2 = None self.prev = None self.findTwoNodes(root) self.n1.val,self.n2.val = self.n2.val,self.n1.val def findTwoNodes(self,root): if root: self.findTwoNodes(root.left) if self.prev and self.prev.val > root.val: if self.n1 == None: self.n1 = self.prev self.n2 = root self.prev = root self.findTwoNodes(root.right)
转载地址：http://iuhzb.baihongyu.com/