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?

要求找到BST中放錯位置的兩個節點.

直觀思路是使用中序遍歷來解.一顆正常的BST,它的正常中序遍歷序列是遞增序列(非遞減,如果有重復元素).所以如果有元素被交換,則會出現遞減的情況.如果不是前后繼的兩個節點,則只會出現一次顛倒的情況,而如果不是前后繼,則會出現兩次,舉例如下:

1 2 3 4 5 6 7這是一個正常的BST中序遍歷序列.如果是前后繼的兩個節點,比如3,4交換,則中序遍歷序列是: 1 2 4 3 5 6 7. 4 3出現一次逆序. 如果不是前后繼,比如3,5交換,則中序遍歷為1 2 5 4 3 6 7. 則5 4, 4 3是兩次逆序.可以看出在第一個逆序對里前面一個值是第一個逆序節點.而在后一個逆序對里后一個值是逆序節點. 而在僅有一個逆序對的情況下,前一個值為第一個逆序節點,后一個值為第二個逆序節點. 時間復雜度為O(n).空間復雜度為O(nlogn).代碼如下:

# 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."""if not root:returnstack = []prev = TreeNode(-sys.maxint-1)cur = rootformer = Nonelatter = Nonewhile stack or cur:if cur:stack.append(cur)cur = cur.leftelse:cur = stack.pop()if cur.val < prev.val:if not former:former = prevlatter = curprev = curelse:latter = curbreakelse:prev = curcur = cur.rightformer.val, latter.val = latter.val, former.val

題目要求的O(1)空間復雜度需要結合morris遍歷來做, 詳見http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html