[leetcode]Recover Binary Search Tree

新博文地址：[leetcode]Recover Binary Search Tree

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?

 这道题想复杂了，上午花了一个多小时都没弄出来，晚上换了一种思路，不到半小时就AC了，总的来说，判断是不是BST还是中序遍历最方便，但是题中说道O(n)复杂度太easy，要求开常量空间。

具体的思路，还是通过中序遍历，只不过，不需要存储每个节点，只需要存一个前驱即可。

例如1,4,3,2,5,6

1.当我们读到4的时候，发现是正序的，不做处理

2.但是遇到3时，发现逆序，将4存为第一个错误节点，3存为第二个错误节点

3.继续往后，发现3，2又是逆序了，那么将第2个错误节点更新为2

如果是这样的序列：1,4,3,5,6同上，得到逆序的两个节点为4和3。

同理对于边界情况也是可以处理的，例如2,1

    TreeNode first = null,second = null,pre = null;
    public void recoverTree(TreeNode root) {
		findNode(root);
		swap(first, second);
	}
	private void findNode(TreeNode root){
		if(root == null){
			return;
		}
		if(root.left != null )  findNode(root.left);
		if(pre != null && root.val < pre.val){
			if(first == null){
				first = pre;
			}
			second = root;
		}
		pre = root;
		if(root.right != null)  findNode(root.right);
	}
	private void swap(TreeNode node1,TreeNode node2){
		int tem = node1.val;
		node1.val = node2.val;
		node2.val = tem;
	}

 以上