本文共 1617 字，大约阅读时间需要 5 分钟。

leetcode 99   Recover Binary Search Tree

题目描述：

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. 分析： 正确的二叉树中序遍历应该是递增，而交换了两个节点后会导致有 0处（交换的2个节点的值相等）或1处（交换的2个节点相邻且其值不相等）或2处（交换的2个节点不相邻且其值不相等）某节点值小于其前一个节点的值，找出错误的节点，最后交换即可。 Python代码：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def recoverTree(self, root):        """        :type root: TreeNode        :rtype: void Do not return anything, modify root in-place instead.        """        #为Solution类添加数据成员precursor，用于在中序遍历树的过程中，指向当前节点的前驱节点。        self.precursor=None         ''' precursor初始值必须指定为None，随着不断的递归调用recursive_left_root_right()函数，        precursor第一次被赋值指向二叉搜索树的最左节点（注意，不是最左叶节点。最左节点和最左叶节点可能不是同一个节点）'''                #为Solution类添加数据成员mistake1和mistake2，用于指向错误的两个节点        self.mistake1=None        self.mistake2=None        self.recursive_left_root_right(root) #调用相应函数，找到错误的节点        self.mistake1.val,self.mistake2.val=self.mistake2.val,self.mistake1.val #交换2个错误节点的值，使二叉搜索树恢复正常            def recursive_left_root_right(self,root):        if root==None:            return         self.recursive_left_root_right(root.left) #递归地中序遍历左子树                if self.precursor!=None and self.precursor.val>root.val:            if not self.mistake1:                self.mistake1,self.mistake2=self.precursor,root            else:                self.mistake2=root        self.precursor=root                self.recursive_left_root_right(root.right) #递归地中序遍历右子树

（完）

转载地址：http://odyai.baihongyu.com/