java - 为什么二叉搜索树有效性的解决方案不起作用？

Question

我编写了一个使用 LinkedList 检查二叉搜索树有效性的解决方案，它证明了有关有效性的错误信息。我检查了有效的 BST，结果返回该树无效。代码如下，

public static boolean isValidBST_( Node root ){

  boolean bol = false;
  LinkedList<Node> queue = new LinkedList<Node>();

  queue.add(root);

  while( !queue.isEmpty() ){

    Node cur = queue.poll();

    if ( ( cur.left != null && cur.data > cur.left.data ) || (cur.right != null && cur.data < cur.right.data  ) ){

      return bol;
    }

    if ( cur.left != null ){

       queue.offer(cur.left);
    }

    if ( cur.right != null ){

      queue.offer(cur.right);
    }

  } // WHILE


  if (queue.isEmpty() ){

    bol = true;
  }

  return bol; 

}

如何改进代码？

我从 main 进行如下调用，

public static void main (String[] args ){


 Node root = new Node(5);
 root.left = new Node(3);
 root.right = new Node(7); 


 root.left.left = new Node(1);
 root.left.right = new Node(4);

 root.right.left = new Node(6);
 root.right.right = new Node(9);

 System.out.println("Does the inserted BST is valid ?  Answer:  " + isValidBST_(root));

}

Answer 1

您的支票似乎有误:

if ( ( cur.left != null && cur.data > cur.left.data ) || (cur.right != null && cur.data < cur.right.data  ) )

当节点的数据大于左侧节点的数据或小于右侧节点的数据时，将通过(并返回false)。你想要相反的。尝试扭转不平等现象。

您问“如何改进代码”。这似乎迫切需要递归:

boolean isValid(Node node) {
    if (node.left != null && (cur.data < node.left.data || !isValid(node.left)))
        return false;
    else if (node.right != null && (cur.data > node.right.data || !isValid(node.right)))
        return false;
    else
        return true;
}

如果您想坚持使用迭代方法，您可以通过删除 bol 变量并删除最终检查来简化:

public boolean isValid(Node root) {
    LinkedList<Node> nodesToCheck = new LinkedList<>();
    nodesToCheck.offer(root);
    while (!nodesToCheck.isEmpty()) {
        Node current = nodesToCheck.poll();
        if (current.left != null) {
            if (current.data < current.left.data)
                return false;
            nodesToCheck.offer(current.left);
        }
        if (current.right != null) {
            if (current.data > current.right.data)
                return false;
            nodesToCheck.offer(current.right);
        }
    }
    return true;
}