领扣LintCode算法问题答案-95. 验证二叉查找树
目录
95. 验证二叉查找树描述样例 1：样例 2：
题解鸣谢
95. 验证二叉查找树
描述
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。
样例 1：
输入：{-1}
输出：true
解释：
二叉树如下(仅有一个节点）:
-1
这是二叉查找树。
样例 2：
输入：{2,1,4,#,#,3,5}
输出：true
解释：
二叉树如下：
2
/ \
1 4
/ \
3 5
这是二叉查找树。
题解
public class Solution {
public boolean isValidBST(TreeNode root
) {
ValidBSTRet ret
= checkValidBST(root
);
return ret
.valid
;
}
private ValidBSTRet
checkValidBST(TreeNode root
) {
if (root
== null
) {
return new ValidBSTRet(true, Integer
.MAX_VALUE
, Integer
.MIN_VALUE
);
}
int min
= root
.val
;
int max
= root
.val
;
if (root
.left
!= null
) {
if (root
.left
.val
> root
.val
) {
return new ValidBSTRet(false, 0, 0);
}
ValidBSTRet ret
= this.checkValidBST(root
.left
);
if (!ret
.valid
) {
return ret
;
}
if (ret
.getMax() >= root
.val
) {
return new ValidBSTRet(false, 0, 0);
}
min
= ret
.getMin();
}
if (root
.right
!= null
) {
if (root
.right
.val
< root
.val
) {
return new ValidBSTRet(false, 0, 0);
}
ValidBSTRet ret
= this.checkValidBST(root
.right
);
if (!ret
.valid
) {
return ret
;
}
if (ret
.getMin() <= root
.val
) {
return new ValidBSTRet(false, 0, 0);
}
max
= ret
.getMax();
}
return new ValidBSTRet(true, min
, max
);
}
class ValidBSTRet {
private boolean valid
;
private int min
;
private int max
;
public ValidBSTRet(boolean valid
, int min
, int max
) {
this.valid
= valid
;
this.min
= min
;
this.max
= max
;
}
public boolean isValid() {
return valid
;
}
public void setValid(boolean valid
) {
this.valid
= valid
;
}
public int getMin() {
return min
;
}
public void setMin(int min
) {
this.min
= min
;
}
public int getMax() {
return max
;
}
public void setMax(int max
) {
this.max
= max
;
}
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
