BST中序遍历就是一个sorted list, 要求O(1) space, 经1楼提醒, 用first, second两个变量记录可能交换的节点即可。如果只有一个降序对(如20, 10, 30, 40, 50), 用first, second记录。如果有两个降序对(如10, 40, 30, 20, 50或50, 20, 30, 40, 10), 用第二个降序对中小的数更新second。while循环中19~23行换成"print root.val"就是非递归的中序遍历。

The result of BST inorder traversal is a sorted list. This problem requires O(1) space, according to the first comment below, only two variables (first, second) are enough to record nodes to be exchanged. If there's only one descending order pair (e.g. 20, 10, 30, 40, 50), use first & second to record it. If there are two descending order pairs (e.g. 10, 40, 30, 20, 50 or 50, 20, 30, 40, 10), use the smaller number in second pair to update second. If we change line 19-23 in while loop to "print root.val", then it's non-recursive inorder traversal of binary tree.

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a tree node
    def recoverTree(self, root):
        originalRoot, stack = root, []
        prev = first = second = None
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                if prev and root.val < prev.val:
                    if first == None:
                        first, second = prev, root
                    else:
                        second = root
                prev, root = root, root.right
        first.val, second.val = second.val, first.val
        return originalRoot