Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    TreeNode firstNode;    TreeNode secondNode;    TreeNode pre;    public void recoverTree(TreeNode root) {        //对于二叉搜索树来讲，中序遍历应该是递增的，本题要求O(1)空间，出发点就是中序遍历的变形        //在中序遍历的过程中，需要找到fisrtWrongNode和secondWrongNode，本题最主要的是，使用pre全局遍历，        /*递归的时候使得pre=root，达到pre能够保存root前置节点的作用，通过比较root和pre的值，找到逆序对，        如果两个数相邻置换，则逆序对只有一个，        如果两个数不相邻，逆序对有两个，此时需要更新secondWrongNode*/        if(root==null) return;        inOrder(root);        swap(firstNode,secondNode);    }    public void inOrder(TreeNode root){        if(root==null) return;        inOrder(root.left);       /* if(pre!=null&&firstNode==null&&root.val