99.md

99. 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?

my thoughts:

1. recursion or iterative to traverse the tree. once a violation of BST invariant is found, store the two pointers to the two nodes; if a second violation is found, update the second pointer to the second node of this case, we can stop by now. swap the val of the two pointers.
O(n)

my solution:

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

class Solution:
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root or (not root.left and not root.right):
            return
        stack = []
        prev, first, second = None, None, None
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if prev and prev.val >= root.val:
                if not first:
                    first = prev
                    second = root
                else:
                    second = root
                    break
            prev = root
            root = root.right
        first.val, second.val = second.val, first.val
        return        

my comments:

from other ppl's solution:

1. N/A