题目：二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
思路：
由于二叉搜索树的中序遍历是递增的，所以可以通过中序遍历找出这两个节点，之后将两节点的值交换。
源码：GitHub源码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode firstNode = null;
TreeNode secondNode = null;
TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
in_order(root);
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
private void in_order(TreeNode root) {
if (root == null) return;
in_order(root.left);
if (firstNode == null && preNode.val > root.val) firstNode = preNode;
if (firstNode != null && preNode.val > root.val) secondNode = root;
preNode = root;
in_order(root.right);
}
}
