Recover Binary Search Tree @LeetCode

package Level4;

import Utility.TreeNode;

/**
 * Recover Binary Search Tree
 * 
 *  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 
confused what "{1,#,2,3}" means  > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 *
 */
public class S99 {

	public static void main(String[] args) {

	}
	
	TreeNode pre;		// 指向当前遍历元素的前一个
	TreeNode first;	// 第一个乱序的元素
	TreeNode second;// 第二个乱序的元素
	
	public void inorder(TreeNode root){
		if(root == null){
			return;
		}
		inorder(root.left);
		if(pre == null){
			pre = root;
		}else{
			if(pre.val >





 root.val){
				if(first == null){
					first = pre;		// 找到第一个乱序的元素
				}
				second = root;		// 第二个乱序的元素。如果用了else，则无法通过只有两个元素的情况
			}
			pre = root;				// 继续搜索
		}
		inorder(root.right);
	}
	
	public void recoverTree(TreeNode root) {
		pre = null;			// 必须在这里初始化一遍，否则OJ会报错
		first = null;
		second = null;
        inorder(root);
        if(first!=null && second!=null){		// 只需要交换元素值，而没必要进行指针操作！
        	int tmp = first.val;
        	first.val = second.val;
        	second.val = tmp;
        }
    }

}