本文共 1373 字，大约阅读时间需要 4 分钟。

题目来源

题目描述

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

解答一（递归）

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

解答二(中序遍历）

基于方法一中提及的性质，我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是.

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

转载地址：http://jnlzi.baihongyu.com/