LeetCode 二叉搜索树系列 ~ 验证二叉搜索树

LeetCode 二叉搜索树系列 ~ 验证二叉搜索树携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第5天,点击查看活动详情 LeetCode 二叉搜索树系列 ~ 验证二叉搜索树

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第5天,点击查看活动详情

二叉搜索树的定义

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

题目

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

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

示例

image.png

输入: root = [2,1,3]
输出: true

image.png

输入: root = [5,1,4,null,null,3,6]
输出: false
解释: 根节点的值是 5 ,但是右子节点的值是 4

提示

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

中序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    // 用来保存前一节点元素值
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        // 边界判断
        if(null == root){
            return true;
        }

        // 先递归左节点,找到最左边的节点。后序的节点再进行比较
        if(!isValidBST(root.left) || root.val <= pre){
            return false;
        }
        
        // 更新上一节点元素值
        pre = root.val;

        // 递归比较右边节点
        return isValidBST(root.right);
    }
}

今天的文章LeetCode 二叉搜索树系列 ~ 验证二叉搜索树分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/15058.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注