Почему решение для бинарного дерева поиска не работает?

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; 

}

Как я могу улучшить код?

Я делаю звонок от основной следующим образом,

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