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.

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

思路：因为有两个节点错位， 需要交换回来，最简单的方法就是中序遍历，然后排序即可。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    public void recoverTree(TreeNode root) {
        preOrder(root);
        TreeNode p = null;
        TreeNode q = null;
        if(list.size() < 2)
            return;
        //冒泡排序
        for(int i = 0; i < list.size() -1; i++){
        	boolean flag = true;
        	for(int j = 0; j < list.size() - 1 - i; j++){
        		if(list.get(j).val > list.get(j+1).val){
        			flag = false;
        			int k = list.get(j).val;
        			list.get(j).val = list.get(j+1).val;
        			list.get(j+1).val = k;
        		}
        	}
        	if(flag){
        		break;
        	}
        }
    }
    /**
     * 中序遍历
     */ 
    private void preOrder(TreeNode root){
        if(root == null)
            return;
        preOrder(root.left);
        list.add(root);
        preOrder(root.right);
    }
}

但是题目要求尽量O(1)的空间，故换一种方法，还是中序遍历，不符合要求的节点保存，同时记录父节点，如果不符合要求的节点只有一个，则说明另一个节点为父节点。

具体代码如下“：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	TreeNode parent = null;
	TreeNode p = null;
    TreeNode q = null;
    public void recoverTree(TreeNode root) {
    	//参考资料：http://blog.****.net/worldwindjp/article/details/21694179
        check(root);
        if(p != null && q != null){
        	int k = p.val;
        	p.val = q.val;
        	q.val = k;
        }
    }
    /**
     * 中序遍历
     */
    private void check(TreeNode root){
    	if(root == null)
    		return;
    	if(root.left != null){
    		check(root.left);
    	}
    	//这段代码是重点
    	//parent是左子树父节点
    	if(parent != null && parent.val > root.val){
    		if(p == null){
    			p = parent;
    			q = root;
    		}else{
    			q = root;
    		}
    	}
    	parent = root;
    	if(root.right != null){
    		check(root.right);
    	}
    }
}