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?

链接： http://leetcode.com/problems/recover-binary-search-tree/

题解：

恢复BST。和上一题validate BST一样，可以使用recursive的 in-order traversal。先递归查找左子树里root.val < prevNode.val的，确定第一个逆序的节点，之后继续搜索，查找第二个逆序的节点。注意不可以在第一次找到第二个逆序的时候就返回了，要继续查找。否则像[2, 3, 1]这样的case会通不过，因为直接就把2和3 swap了，并没有找到1。最后把两个节点的val交换一下就可以了。

Time Complexity - O(n)， Space Complexity - O(1)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode firstNode;
    TreeNode secondNode;
    TreeNode lastNode;
    
    public void recoverTree(TreeNode root) {
        this.lastNode = new TreeNode(Integer.MIN_VALUE);
        inorderTraversal(root);
        int tmp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = tmp;
    }
    
    private void inorderTraversal(TreeNode root) {
        if(root == null)
            return;
        inorderTraversal(root.left);
        if(firstNode == null && this.lastNode.val >= root.val)
            firstNode = lastNode;
        if(firstNode != null && this.lastNode.val >= root.val)
            secondNode = root;
        this.lastNode = root;
        inorderTraversal(root.right);
    }
}

Update:

想了一下，不用初始化lastNode = new TreeNode(Integer.MIN_VALUE)。当然初始化也可以，it doesn't matter。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode firstNode;
    TreeNode secondNode;
    TreeNode lastNode;
    
    public void recoverTree(TreeNode root) {
        inorderTraversal(root);
        int tmp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = tmp;
    }
    
    private void inorderTraversal(TreeNode root) {
        if(root == null)
            return;
        inorderTraversal(root.left);
        if(lastNode != null && firstNode == null && lastNode.val >= root.val) 
            firstNode = lastNode;
        if(lastNode != null && firstNode != null && lastNode.val >= root.val) 
            secondNode = root;
        lastNode = root;
        inorderTraversal(root.right);
    }
}

Reference：

https://leetcode.com/discuss/13034/no-fancy-algorithm-just-simple-and-powerful-order-traversal

https://leetcode.com/discuss/7319/an-elegent-time-complexity-and-space-complexity-algorithm

https://leetcode.com/discuss/41182/tree-deserializer-and-visualizer-for-python

https://leetcode.com/discuss/31543/a-concise-java-solution-using-morris-inorder-o-time-o-1-space

https://leetcode.com/discuss/26310/detail-explain-about-morris-traversal-finds-incorrect-pointer

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html