LeetCode 99 Recover Binary Search Tree

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.

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

思路;遞歸。使用遞歸查找左子樹的最大節點，使用遞歸查找右子樹的最小節點；

1若左子樹的最大節點的值比右子樹的最小節點大，說明是左子樹的最大節點與右子樹的最小節點進行了交換；

2若若左子樹的最大節點的值比根節點大，說明是根節點與左子樹的最大節點進行了交換；

3若若右子樹的最大節點的值比根節點小，說明是根節點與右子樹的最小節點進行了交換；

4若上述三種情況均沒有發生，則說明左子樹的某兩個節點進行了交換或者右子樹的某兩個節點進行了交換，遞歸查看左子樹和右子樹是否有節點進行了交換；

public class Solution {
	private TreeNode findMin(TreeNode root) {
		TreeNode result, l = root, r = root;
		if (root.left != null)
			l = findMin(root.left);
		if (root.right!= null)
			r = findMin(root.right);
		result = l.val < r.val ? l : r;
		return result.val < root.val ? result : root;
	}

	private TreeNode findMax(TreeNode root) {
		TreeNode result, l = root, r = root;
		if (root.left != null)
			l = findMax(root.left);
		if (root.right != null)
			r = findMax(root.right);
		result = l.val > r.val ? l : r;
		return result.val > root.val ? result : root;
	}

	public void recoverTree(TreeNode root) {
		TreeNode l=root,r=root;
		if(root==null||(root.left==null&&root.right==null)) return;
		if(root.left!=null) l=findMax(root.left);
		if(root.right!=null) r=findMin(root.right);
		
		if(l.val>r.val){
			int temp=l.val;
			l.val=r.val;
			r.val=temp;
			return ;
		}else if(l.val>root.val){
			int temp=l.val;
			l.val=root.val;
			root.val=temp;
			return ;
		}else if(r.val