本题不算非常难，想明白后就是介于Easy和Medium之间。。但是第一次做比较难作出完美的抽象，所以非常值得学习。。
    首先，我们需要“忘掉”这是个Tree，要想像成一个sorted array，比如：[1, 2, 3, 4, 5, 6]

    • 一个Binary Search Tree，只有做inorder traversal就会打印出sorted array
    • Two element of BST are swapped by mistake，可以理解成数组中的两个元素swap：
    • [1, 2, 4, 3, 5, 6]: 相邻元素swap，即只有一次99. Recover Binary Search Tree[没有解出] - 图1
    • [1, 6, 3, 4, 5, 2]: 不相邻元素swap，此时有两次，分别找到即可99. Recover Binary Search Tree[没有解出] - 图2

    本题一点也不难，代码如下:

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.   private TreeNode prev;
    12.   private TreeNode first;
    13.   private TreeNode second;
    15.   public void recoverTree(TreeNode root) {
    16.     inorder(root);
    18.     int val = first.val;
    19.     first.val = second.val;
    20.     second.val = val;
    21.   }
    23.   private void inorder(TreeNode node) {
    24.     if (node.left != null) {
    25.       inorder(node.left);
    26.     }
    28.     if (prev != null && node.val < prev.val ) {
    29.       if (first == null) {
    30.         first = prev;
    31.       }
    32.       if (first != null) {
    33.         second = node;
    34.       }
    35.     }
    36.     prev = node;
    38.     if (node.right != null) {
    39.       inorder(node.right);
    40.     }
    41.   }
    42. }