二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
输出: [3,1,null,null,2]
示例 2:
输入: [3,1,4,null,null,2]
输出: [2,1,4,null,null,3]
进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？
解
此题的解题关键在于二叉搜索树的中序遍历结果是有序。那么递归地中序遍历树，使用pre记录遍历节点的父节点，若父节点的值大于当前节点的值，说明该处就是需要交换的地方，分别使用p1和p2指针记录下来。又由题目可知原树中只有一处需要交换，那么当p1不为空时，说明已经遍历到结果了，不需用在交换。
TreeNode p1,p2,pre;
public void recoverTree(TreeNode root) {
mid_order(root);
int temp = p1.val;
p1.val = p2.val;
p2.val = temp;
}
public void mid_order(TreeNode root) {
if(root==null)
return;
mid_order(root.left);
if(pre!=null&&pre.val>root.val) {
if(p1==null)
p1 = pre;
p2 = root;
}
pre = root;
mid_order(root.right);
}
