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

Question

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

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  ) )

当节点数据大于左节点数据或小于右节点数据时，

将通过（和return false）。你想要相反的。尝试扭转不平等现象。

你问了'how to improve the code'。这似乎是在呼唤递归：

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

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

Why the solution for binary search tree validity is not working?

java

binary-search-tree