сбалансированное () двоичное дерево

Question

Мне нужно написать метод, который определяет, является ли двоичное дерево сбалансированным. Итак, сначала я должен определить высоту каждой стороны дерева. Но у меня возникают проблемы с пониманием того, как я собираюсь подсчитать максимальную длину поддерева, не считая все узлы в поддереве. Мне очень сложно задать этот вопрос, поэтому вы, ребята, можете понять.

// primary method
public int Height()
{
    int h = height( root );
}

// recursive method
private int height( Node x )
{
    if( x == null ) return 0;
    count++;                   
    height( x.left );
    height( x.right );
    return count;           
}

Вот мой код для расчета максимальной высоты дерева. Но я не знаю, как определить высоту левой или правой стороны, и этот метод, кажется, подсчитывает количество узлов в самом дереве.

Answer 1

Высота равна 1 + макс (left.height (), right.height ()).

Вы должны вернуть значение вместо значение aпеременная (count, в вашем случае), иначе вы сойдете с ума.

Answer 2

Этот метод даже не скомпилируется из-за оператора return; - вам нужно вернуть int.

Итак, if(x == null), что вы должны вернуть? Какова высота пустого дерева?

Как только вы выяснили это, представьте, что у вашего корня есть только левое поддерево (root.right == null), и вы знаете высоту левого поддерева. Какой должна быть высота всего дерева?

Что если у него только правильное поддерево?

А что если у него есть оба?

Обратите внимание, что вам не нужна глобальная переменная счета для всего этого.

Answer 3

Добавляя к подсказкам, я также укажу, что вы действительно хотите использовать рекурсию.

Answer 4

Высота узла на единицу больше высоты его самого высокого подузла (подсказка: используйте Math.max).