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

【每天学习一点算法 2025/12/17】验证二叉搜索树

news 2026/7/1 22:34:17

每天学习一点算法 2025/12/17

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

根据题目描述可以知道二叉搜索树，使用中序遍历的结果数组一定是升序，也就是每一次遍历的节点值都比之前的大，我们只需要在遍历过程比较一下当前节点值是否符合要求即可。

functionisValidBST(root:TreeNode|null):boolean{constresult:number[]=[]// 用于存储遍历值// 为了避免result全局污染添加一个辅助函数functionvalidate(node:TreeNode|null):boolean{if(node===null)returntrue;// 初始默认为有效搜索二叉树// 提前中断已经无效的情况if(!validate(node.left)){returnfalse}// 判断当前节点是否符合二叉搜索树特征if(result.filter(item=>item>=node.val).length>0)returnfalseresult.push(node.val)// 提前中断已经无效的情况if(!validate(node.right)){returnfalse}returntrue}// 调用辅助函数returnvalidate(root);};

之前的二叉树相关的题我们也提到了递归的每次一层的root其实就是当前子树的根节点，我们只需要在每一层的遍历中判断当前节点的值和子节点的大小关系即可知道这是否是有效的二叉搜索树。

functionisValidBST(root:TreeNode|null):boolean{// 辅助函数，增加上下界参数functionvalidate(node:TreeNode|null,lower:number,upper:number):boolean{if(node===null)returntrue;// 终止时无超出上下界的结果为有效// 检查当前节点值是否超出上下界if(node.val<=lower||node.val>=upper){returnfalse;}// 递归检查左子树和右子树returnvalidate(node.left,lower,node.val)&&validate(node.right,node.val,upper);}// 调用辅助函数，初始上下界为负无穷到正无穷returnvalidate(root,-Infinity,Infinity);};