public boolean isValidBST(TreeNode root) {
int[] minmax = new int[2];
return isBST(root, minmax);
}
public boolean isBST(TreeNode root, int[] minmax) {
if (root == null) { // 空树也算是 BST
return true;
}
if (root.left == null && root.right == null) {
minmax[0] = root.val;
minmax[1] = root.val;
return true;
}
// 当左子树为空时,以root为根的树的 minLeft maxLeft 的值
int minLeft = root.val;
int maxLeft = root.val;
boolean result = true;
if (root.left != null) {
result = isBST(root.left, minmax);
if (!result) return false; // 左子树都不是 BST了，直接返回
minLeft = minmax[0];
maxLeft = minmax[1];
// 比左子树最大值小
if (root.val <= maxLeft) {
return false;
}
}
// 当右子树为空时，minRight、maxRight的值
int minRight = root.val;
int maxRight = root.val;
if (root.right != null) {
result = isBST(root.right, minmax);
if (!result) return false; // 右子树都不是 BST了，直接返回
minRight = minmax[0];
maxRight = minmax[1];
if (root.val >= minRight) {
return false;
}
}
// 还能到达者说明是 BST 了
minmax[0] = minLeft;
minmax[1] = maxRight; // 更改以节点 root 为BST的最小值、最大值
return true;
}
判断树是否是二叉搜索树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 《剑指offer》24题：Tips：如果面试题是要求处理一棵二叉树的遍历序列，我们可以先找到二叉树的根节点，再基于...
- 简单来说, 完全二叉树是指按照层次进行遍历的时候所得到的序列与满二叉树相对应 这里提供两种思路和相应的代码: 1....
- 对于如下一颗树，如何判断它是否符合搜索二叉树 首先，要明白搜索二叉树的特点：1，根节点的所有左节点的值小于根节点，...
- 需求 在项目中需要用到不依赖Activity Context启动的Dialog，并且Dialog的显示层级要在最顶...
- 作者：毛志杰 导读：当中小学生能掌握这种“以物喻人”的写作手法时，恭喜你，作文水平一定超越99%的同学！ 前几天，...
