美文网首页leetcode
leetcode98-一个二叉树,判断其是否是一个有效的二叉搜索

leetcode98-一个二叉树,判断其是否是一个有效的二叉搜索

作者: 五年老码农 | 来源:发表于2020-02-13 22:33 被阅读0次

    题目:

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

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

    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
    示例 1:
    输入:


    树1.PNG

    输出: true
    示例 2:
    输入:


    树2.PNG

    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
    根节点的值为 5 ,但是其右子节点值为 4
    中序遍历解决

    代码:

    //中序编列验证二叉搜索树
    class Solution {
        public boolean isValidBST(TreeNode root) {
            //定义一个栈
            Stack<TreeNode> sstack = new Stack();
            double min =  -Double.MAX_VALUE;
            while(root!=null||!sstack.isEmpty()){
                while(root!=null){
                    sstack.push(root);
                    root = root.left;
                }
                root =sstack.pop();
                if(root.val<=min){
                    return false;
                }
                min =Double.valueOf(root.val);
                root =root.right;
            }
            return true;
        }
    }
    

    相关文章

      网友评论

        本文标题:leetcode98-一个二叉树,判断其是否是一个有效的二叉搜索

        本文链接:https://www.haomeiwen.com/subject/xerrfhtx.html