Given a Binary Search Tree with only two nodes swapped. Try to find them and recover the binary search tree.

Input:

           4

          / \

         2   6  

        / \   / \

       1  5 3  7

Output: 4

              / \

            2   6

           /  \   / \

        1  3   5  7

Input:

           3

          / 

         2     

          \   

           1

Output: 3

              / 

            1  

              \  

                2

Solution: 用inorder遍历，顺序应该递增。用prev, first, second记录，当遇到prev.key > root.key时，first一定是prev, second一定是root

TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;

public void recoverTree(TreeNode root) {    
    inOrder(root);
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}

public void inOrder(TreeNode root){
    if(root == null) return;
    //search left tree
    inOrder(root.left);

    //in inorder traversal of BST, prev should always have smaller value than current value
    if(prev != null && prev.val >= root.val){
        //incorrect smaller node is always found as prev node
        if(first == null) first = prev;
      //incorrect larger node is always found as curr(root) node
        second = root;
    }


    //update prev node
    prev = root;

    //search right tree
    inOrder(root.right);
}

或者：

TreeNode firstElement = null;
    TreeNode secondElement = null;
    // The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
    TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {

        // In order traversal to find the two elements
        traverse(root);

        // Swap the values of the two nodes
        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }

    private void traverse(TreeNode root) {

        if (root == null)
            return;

        traverse(root.left);

        // Start of "do some business", 
        // If first element has not been found, assign it to prevElement (refer to 6 in the example above)
        if (firstElement == null && prevElement.val >= root.val) {
            firstElement = prevElement;
        }

        // If first element is found, assign the second element to the root (refer to 2 in the example above)
        if (firstElement != null && prevElement.val >= root.val) {
            secondElement = root;
        }        
        prevElement = root;

        // End of "do some business"

        traverse(root.right);
}

错误：把root.key与list最后一个元素比较

  boolean found = false;
  TreeNode first = null, second = null;
  public TreeNode recover(TreeNode root) {
    List<TreeNode> res = new ArrayList<>();
    inorder(root, res);
    if (first != null && second != null) {
      int temp = first.key;
      first.key = second.key;
      second.key = temp;
    }
    return root;
  }
  private void inorder(TreeNode root) {
    if (root == null || found) {
      return;
    }
    inorder(root.left);
    if (res.size() > 0 && res.get(res.size() - 1).key > root.key) {
      if (first == null) {
        first = root;
      } else {
        second = root;
        found = true;
      }
    }

    res.add(root);

    inorder(root.right);
  }