我正在尝试解决此问题,但遇到一些麻烦:
在二叉搜索树(BST)中:
- 节点左子树中每个节点的数据值小于该节点的数据值。
- 节点的右子树中每个节点的数据值都大于该节点的数据值。
给定根节点:
class Node { int data; Node left; Node right; }
确定二叉树是否也是二叉搜索树
我有以下代码:
boolean check(Node root) {
//node doesn't have any children
if (root.left == null && root.right == null) {
return true;
}
boolean leftIsBst = true;
boolean rightIsBst = true;
if (root.left != null) {
leftIsBst = (root.left.data < root.data) && check(root.left);
}
if (root.right != null) {
rightIsBst = (root.right.data > root.data) && check(root.right);
}
return leftIsBst && rightIsBst;
}
在某些情况下,这是可行的,但在这种情况下,它会失败:
如您所见,节点(4)在节点(3)的左子树中,尽管4大于3,所以该方法应返回false
。我的代码返回了true
。
我该如何控制这种情况?如何检查左/右子树中的所有值都比根(而不是直接子代)低/大?
您的定义是正确的(尽管不一定需要坚持所有键都是不同的),但是您的代码并没有实现定义中的所有条件。具体来说,您不必在每个子树中强制使用最小值和最大值。
这是一个有效的递归解决方案,可实现您的定义:
boolean check(Node root) {
return check(root, INT_MIN, INT_MAX);
}
boolean check(Node n, int minval, int maxval) {
if (n == null) {
return true;
}
return (
n.data >= minval && n.data <= maxval &&
check(n.left, minval, n.data-1) &&
check(n.right, n.data+1, maxval)
);
}
请注意,我并没有费心检查n.data-1
and中的溢出n.data+1
,这在现实生活中是必须要做的。如果要允许重复的密钥,只需将其更改为,n.data
而不必担心。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句