当前位置：首页 > article >正文

leetcode98-验证二叉搜索树

article 2025/3/20 19:43:52

leetcode 98
在这里插入图片描述
这里要验证二叉搜索树的关键是知道二叉搜索树的特性：

节点的左子树只包含小于当前节点的值
节点的右子树只包含大于当前节点的值
所有左子树和右子树自身必须也是二叉搜索树
根据这些特性，可以知道，如果使用中序遍历：左中右，得到的是从小到大排序的，那说明是二叉搜索树

我们可以默认先把这个二叉树当成是二叉搜索树，所以初始化设置result = true
由于二叉搜索树中序遍历后的结果是递增的，我们初始化maxValue = -Infinity，用于存储上次的节点值，下一个节点值就一定是大于maxValue的，否则就不是二叉搜索树 - > 修改result = false
如果下一个值更大，那么更新maxValue

var isValidBST = function(root) {
   let result = true;
   let maxValue = -Infinity;
   const deep = (root) => {
       if(!root) return
       result && root.left && deep(root.left)
       if(maxValue >= root.val){
           result = false;
       }else{
       	maxValue = root.val;
       }
       result && root.right && deep(root.right)
   }
   deep(root)
   return result;
};