Найти, сколько узлов на определенной высоте в левом дочернем и правом дереве родного брата?

Question

Я пытаюсь попрактиковаться с представлением дерева слева-справа-потомком, и я действительно не могу понять, как найти число узлов с заданной высотой.

    10 
    | 
    2 -> 3 -> 4 -> 5 
              |    | 
              6    7 -> 8 -> 9  

Например, если я выбираю высоту 0, функция должна вернуть 1 (потому что на высоте 0 у меня есть только 1 узел, который является корнем, в данном случае 10), если я выбираю высоту 1, он должен вернуть 4 (4 узла), если я выберу высоту 2, то он также должен вернуть 4.

Answer 1

Recurse:

• Если дерево пустое, оно равно 0.
• Если высота H равна 0, это 1 + количество братьев и сестер.
• В противном случае это сумма узлов на высоте H-1 у дочернего элемента и на высоте H у братьев и сестер.