leetcode-99 Recover_Binary_Search_Tree
题目要求：
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;