恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例1:
image.png
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例2:
image.png
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
思路：
利用二叉搜索树中序遍历是有序的特点，找出两个错误的节点的位置，记录下来，然后待遍历结束之后交换两个节点的值。空间复杂度：O(h)，h是树的高度，也是递归调用中产生的递归栈的数目。
代码：
class Solution {
private TreeNode prev;
private TreeNode nodeX;
private TreeNode nodeY;
public void recoverTree(TreeNode root) {
inOrderAndSort(root);
if(nodeY!=null&&nodeX!=null){
int temp=nodeX.val;
nodeX.val=nodeY.val;
nodeY.val=temp;
}
}
public void inOrderAndSort(TreeNode node){
if(node == null){return;}
inOrderAndSort(node.left);
if(prev == null){}
else{
if(node.val<prev.val){
if(nodeX==null) {
nodeX = prev;
}
// 这里无论nodeX在此前是否为null，都要把nodeY赋值为node，
// 这是因为如果是两个连续节点值需要交换，
// 按照这种方式，不会遗漏这种情况，同时如果并不是这两个连续节点的值要交换，
// 那么之后遍历的过程中也会更新nodeY的值
nodeY=node;
}
}
prev=node;
inOrderAndSort(node.right);
}
}
