恢复二叉搜索树

给你二叉搜索树的根节点 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);
    }
}