Проверка того, сбалансировано ли двоичное дерево

Question

Я видел вопрос в книге (Cracking the Coding Interview). Предлагаемый код:

public boolean isBalanced(Node root) { 

    if(root == null) 
     return true; 

    int leftHeight = getHeight(root.left); 
    System.out.println("left height: " + leftHeight); 
    int rightHeight = getHeight(root.right); 
    System.out.println("right height: " + rightHeight); 
    int diff = Math.abs(leftHeight - rightHeight); 

    // check if difference in height is more than 1 
    if (diff > 1) 
     return false; 

    // check if left and right subtrees are balanced 
    else 
     return isBalanced(root.left) && isBalanced(root.right); 

Часть я не понимаю, почему мы обязательно вернуться isBalanced (root.left) & & isBalanced (root.right). Разве не достаточно просто проверить высоту и вернуть false, если высота больше 1, и верно в противном случае?

Answer 1

Нет, этого недостаточно для , чтобы проверить высоту и вернуть значение false, если высота больше 1, а в противном случае -. Просто проверка высоты корня приведет к ложным срабатываниям, подобным следующим:

 A 
    /\ 
     B F 
    //
    C G 
//
    D H 
//
E I