99. Recover Binary Search Tree 恢复二叉搜索树

题目地址：https://leetcode.com/problems/recover-binary-search-tree/description/

题目描述：

Twoelements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

题目大意

删除二叉树中指定一节点，并调整二叉树，使得结果的二叉树仍然满足BST的条件。

解题方法

同学们，看到BST就想什么？对，中序遍历是有序的。

那么，如果其中两个被交换了，那么中序遍历的结果一定也就不对了。比如：

[1, 2, 3, 4, 5, 6]  ==>  [1, 5, 3, 4, 2, 6]

那么，可以看出5这个数字比后面的3大，说明他被打乱了；另外2这个数字，比前面的数字4小，所以他也被打乱了。

所以，可以通过先进行中序遍历得到所有的，然后再查找哪些乱了，再复原，时间复杂度O(n)。

但是，中序遍历的操作不需要完全完成。在中序遍历的过程中，用一个指针保存上个节点，那么当前节点值应该小于前一个节点的值。否则就存在乱序。

第一个乱序的数字是pre，第二个乱序的数字是root，所以用两个指针分别保存。

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.pre, self.first, self.second = None, None, None
        self.inOrder(root)
        self.first.val, self.second.val = self.second.val, self.first.val

    def inOrder(self, root):
        if not root: return
        self.inOrder(root.left)
        if self.pre and self.pre.val > root.val:
            if not self.first:
                self.first = self.pre
            self.second = root
        self.pre = root
        self.inOrder(root.right)

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

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发