题目要求：
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
给出一棵二叉树，其中有两个结点交换了位置，要求找出这两个结点，恢复正确的二叉树。
注意：要求空间复杂度为O(1)
思路：
由于二叉树的中序遍历是升序排列的，因此当交换了两个结点后，再次遍历该二叉树会出现乱序现象。
第一次出现乱序的地方，就是要找的第一个结点；
最后一次出现乱序的地方，就是要找的第二个结点（注意此处说的是最后一次乱序的地方，而不是第二次乱序的地方）。
代码：
if(root == null){
return;
}
//利用中序遍历的上升特性
Stack<TreeNode> ts = new Stack<TreeNode>();
TreeNode ptr = root;
//记录第一次出现乱序的地方
boolean flag = true;
TreeNode sw1 = null, sw2 = null, pre = null;
while( ptr != null || !ts.isEmpty()){
while(ptr != null){
ts.push(ptr);
ptr = ptr.left;
}
if(!ts.isEmpty()){
//栈顶弹栈
ptr = ts.pop();
//第一次出现乱序的地方
if(pre!= null && flag && pre.val > ptr.val){
//此时错误结点为pre
sw1 = pre;
flag = false;
}
//最后一次出现乱序的地方
if(pre != null && pre.val > ptr.val){
//此时错误结点为当前结点ptr
sw2 = ptr;
}
pre = ptr;
ptr = ptr.right;
}
}
int val = sw1.val;
sw1.val = sw2.val;
sw2.val = val;