Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

解题思路：

本题方法多多，可以采用DFS，当然最简答的方法是采用之前的中序遍历检查得到的List是否有序即可。

public boolean isValidBST(TreeNode root) {        List
     
       list=inorderTraversal(root);        if(list.size()==0)            return true;        int temp=list.get(0);        for(int i=1;i
      
       =list.get(i))        		return false;        	temp=list.get(i);        }        return true;    }    public List
       
         inorderTraversal(TreeNode root) {    List
        
          list = new ArrayList
         
          ();    if(root==null)        return list;    if (root.left != null)        list.addAll(inorderTraversal(root.left));    list.add(root.val);    if (root.right != null)        list.addAll(inorderTraversal(root.right));    return list;    }
         
        
       
      
     

 

JAVA实现如下：