给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
�
二叉搜索树有个特性:中序遍历结果是个升序序列
可以利用此特性通过验证树的中序遍历结果是否是升序序列来间接判断树是否二叉搜索树
/**
* 利用二叉搜索树中序遍历结果是个升序序列的特性
* 通过验证树的中序遍历结果是否是升序序列来间接判断树是否二叉搜索树
*
* @param root
* @return
*/
public boolean isValidBST(TreeNode root) {
ArrayList<Integer> valList = new ArrayList<>();
inOrder(root, valList);
// 验证中序遍历结果是否是一个升序序列
boolean isValid = true;
int preVal = valList.get(0);
for (int i = 1; i < valList.size(); i++) {
int curVal = valList.get(i);
if (curVal <= preVal) {
isValid = false;
break;
}
preVal = curVal;
}
return isValid;
}
/**
* 树的中序遍历
* @param node
* @param result
*/
public void inOrder(TreeNode node, ArrayList<Integer> result) {
if (node == null) {
return;
}
inOrder(node.left, result);
result.add(node.val);
inOrder(node.right, result);
}
�
假设有一棵二叉搜索树:
4
/ \
1 6
/ \ / \
0 2 5 7
\
8
�其中序遍历结果:[0, 1, 2, 4, 5, 6, 7, 8]
左子树:
1
/ \
0 2
位于中序遍历结果序列 [0~4) 之间
右子树:
6
/ \
5 7
\
8
位于中序遍历结果序列 (4, 8] 之间
右子树的中序遍历结果序列:[5, 6, 7, 8]
左子树:
5
位于中序遍历结果序列 [5, 6) 之间
右子树:
7
\
8
位于中序遍历结果序列 (6,8] 之间
那么是否可以不断的通过判断节点的值是否位于某个范围值之间从而判断树是否满足二叉搜索树的标准?
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
// 若当前根节点的值小于等于最小值 或者 大于等于最大值 则表示不符合二叉搜索树
if (node.val <= min || node.val >= max) {
return false;
}
// 左子树的最大值不能大于当前根节点 右子树的最小值不能小于当前根节点
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}