JAVA程序设计： 验证二叉搜索树（LeetCode：98）

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

    2

   / \

  1   3

输出: true

示例 2:

输入:

    5

   / \

  1   4

     / \

    3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

     根节点的值为 5 ，但是其右子节点值为 4 。

思路：

方法一：递归，要记得当前左节点或者右节点并不是仅仅和它的父节点比较这么简单。。。。

class Solution { 
    public boolean isValidBST(TreeNode root) {
       
    	return findAns(root,null,null);
    }
    
    private boolean findAns(TreeNode root,Integer lower,Integer upper)
    {
    	if(root==null)
    		return true;
    	
    	int val=root.val;
    	
    	if(lower!=null && lower>=val) return false;
    	if(upper!=null && upper<=val) return false;
    	
    	if(!findAns(root.right,val,upper)) return false;
    	if(!findAns(root.left,lower,val)) return false;
    	
    	return true;
    }
}
           

方法二：迭代，我们可以使用栈进行深度优先搜索

class Solution { 
	
	LinkedList<TreeNode> stack=new LinkedList();
	LinkedList<Integer> lowers=new LinkedList(),uppers=new LinkedList();
	
    public boolean isValidBST(TreeNode root) {
       
    	Integer lower=null,upper=null,val;
    	update(root,lower,upper);
    	
    	while(!stack.isEmpty())
    	{
    		root=stack.poll();
    		lower=lowers.poll();
    		upper=uppers.poll();
    		
    		if(root==null) continue;
    		
    		val=root.val;
    		if(lower!=null && val<=lower) return false;
    		if(upper!=null && val>=upper) return false;
    		
    		update(root.left,lower,val);
    		update(root.right,val,upper);
    	}
    	
    	return true;
    }
    
    private void update(TreeNode root,Integer lower,Integer upper)
    {
    	stack.add(root);
    	lowers.add(lower);
    	uppers.add(upper);
    }
}
           

方法三：采用中序遍历的方法，我们知道中序遍历二叉搜索树得到的序列一定是个有序序列，因此我们遍历完整棵树后只用判断一下是不是一个升序序列即可。

class Solution { 
    public boolean isValidBST(TreeNode root) {
       
    	Stack<TreeNode> st=new Stack<TreeNode>();
    	double inorder=-Double.MAX_VALUE;
    	
    	while(!st.isEmpty() || root!=null)
    	{
    		while(root!=null)
    		{
    			st.push(root);
    			root=root.left;
    		}
    		
    		root=st.pop();
    		
    		if(root.val<=inorder) return false;
    		
    		inorder=root.val;
    		root=root.right;
    	}
    	
    	return true;
    }
}