首页 文章

检查二叉树是否也是二叉搜索树的问题

提问于
浏览 次
5

我正试图解决这个问题，但我遇到了一些麻烦：

在二叉搜索树（BST）中：节点左子树中每个节点的数据值小于该节点的数据值 . 节点右子树中每个节点的数据值大于该节点的数据值 . 给定根节点：class Node {
int数据;
节点离开;
节点权;
}
确定二叉树是否也是二叉搜索树

我有这个代码：

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;
}

这在某些情况下有效，但在以下情况下失败：

enter image description here

如您所见，节点 (4) 位于节点 (3) 的左子树中，尽管4大于3，因此该方法应返回 false . 不过，我的代码返回 true .

我怎么能控制那个案子？如何检查左/右子树中的所有值是否低于/大于根（不仅仅是直接子）？

java algorithm binary-tree binary-search-tree

4 回答

  • 1

    您的定义是正确的（尽管您不一定要坚持所有密钥都是不同的），但您的代码并未实现定义中的所有条件 . 具体而言，您不会在每个子树中强制执行最小值和最大值 .

    这是一个有效的递归解决方案，可以实现您的定义：

    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 和 n.data+1 中检查溢出，这在现实生活中你必须要做 . 如果您想允许重复键，只需将它们更改为 n.data ，您就不必担心它 .

    回复于
  • 1

    像下面这样的东西应该工作

    boolean check(Node root) {   

    if (root == null) {
        return true;
    }


    if (root.left != null && max(root.left) > root.data  ) {
        return false
    }

    if (root.right != null && max(root.right) < root.data ) {
        return false;
    }

    return check(root.left) && check(root.right);
}

    注意：

    • 这效率很低

    • 你需要实施 max()

    回复于
  • 0

    您的递归逻辑不正确 . 我在这里给cpp逻辑 . 您可能需要将其转换为Java代码 .

    bool check（Node * root）{

    static Node *prev = NULL;

if(root) {

    If(!check(root->left)) return false;

    If(prev != Null && prev->data > root->data) return false;

    Prev = root;

    return check(root->right);


}

return true;

    }

    回复于
  • 6

    BST定义为：

    • 节点的左子树始终包含值小于节点值的节点 . - 节点的右子树总是包含值大于节点值的节点 . - 左右子树也是有效的BST .
    class Solution {
        public boolean isValidBST(TreeNode root) {
            return helper (root,Integer.MIN_VALUE,Integer.MAX_VALUE);
        }
        public boolean helper(TreeNode root,long low,long high){
            if (root==null){
                return true;
            }
            if (root.val<low ||root.val>high){
                return false;
            }
            return (helper(root.left,low,root.val-1) && 
    helper(root.right,root.val+1,high));
        }
    }
    回复于

相关问题