Recover Binary Search Tree

题目描述

Two elements 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?

解题方法

O(n) space的方法

做一个in-order traversal, 然后发现顺序错误的两个node，将它们swap回去就可以了

O(1) space

由上面的解法我们可以发现，其实我们并不需要整个in-order的结果，只需要找到这两个在In-order里顺序错乱的node就可以了。 所以我们可以还是做in-order traversal,在这个过程中记录下两个错位的node,然后再将他们swap。但是如果找到这两个点呢， 就像在in-order array中一样，我们需要将它们和prev比较，根据比较结果来判断。

所以， 我们需要一个变量last来计算上一个visit的node

Solution

class Solution(object):
    def __init__(self):
        self.first = None
        self.second = None
        self.last = None

    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.traverse(root)

        tmp = self.first.val
        self.first.val = self.second.val
        self.second.val = tmp

    def traverse(self, root):
        if not root:
            return

        self.traverse(root.left)
        if not self.first and self.last and root.val < self.last.val:
            self.first = self.last

        if self.first and self.last and root.val < self.last.val:
            self.second = root

        self.last = root
        self.traverse(root.right)

Reference

• yu's garden
• yu's coding garden
• 水中的鱼

这到底是不是同一个人……