我要招人在哪个网站招,做网站用哪个软件写比较好,站长工具seo优化,做设备租赁的网站题目描述#xff1a; 给你一个二叉树的根节点 #xff0c;判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下#xff1a; 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得… 题目描述 给你一个二叉树的根节点 判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得更多算法思路:代码文档算法解析的私得。 一个有效的二叉搜索树BST要求对于每个节点其左子树中的所有节点值都要小于当前节点值而其右子树中的所有节点值都要大于当前节点值。同时还要确保每个子树自身也是一个有效的二叉搜索树。 基于这个思想我们可以采用递归的方式来判断一个二叉树是否是有效的二叉搜索树。对于每个节点我们可以限定一个上下界保证其左子树的所有节点值都在这个上下界内而右子树的所有节点值都在另一个上下界内。 具体步骤如下 初始化递归函数传入当前节点、左界限和右界限。如果当前节点为空直接返回 true。如果当前节点值不在左界限和右界限范围内返回 false。对左子树递归调用左界限不变右界限变为当前节点值。对右子树递归调用左界限变为当前节点值右界限不变。如果左子树和右子树都返回 true则说明当前节点及其子树是有效的二叉搜索树。 这个过程递归地向下进行最终判断整棵树是否是有效的二叉搜索树。 运行效果 完整代码 /*** 2 * Author: LJJ* 3 * Date: 2023/8/18 13:32* 4*/
public class ValidateBST {static class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(int val){this.val val;}}// 主函数判断给定二叉树是否为有效二叉搜索树public boolean isValidBST(TreeNode root){// 调用递归函数初始值不限定上界和下界return isValidBST(root,null,null);}// 递归函数判断以当前节点为根的子树是否为有效的二叉搜索树private boolean isValidBST(TreeNode node, Integer lower, Integer upper){// 递归终止条件如果当前节点为空说明子树是一个有效的二叉搜索树if (node null){return true;}int val node.val;// 检查当前结点的是否在合适的范围内if (lower ! null val lower){return false;}if (upper ! null val upper){return false;}// 递归判断左子树和右子树是否是有效的二叉搜索树// 对于左子树当前节点的值成为上界对于右子树当前节点的值成为下界return isValidBST(node.left,lower,val) isValidBST(node.right,val,upper);}public static void main(String[] args) {ValidateBST validateBST new ValidateBST();// 创建示例二叉树TreeNode root new TreeNode(5);root.left new TreeNode(2);root.right new TreeNode(7);root.left.left new TreeNode(1);root.left.right new TreeNode(3);root.right.left new TreeNode(6);root.right.right new TreeNode(8);// 调用验证函数并输出结果boolean isValid validateBST.isValidBST(root);System.out.println(是否为二叉搜索树? isValid); // 输出 true}
}
