Подсчитайте нет дочерних узлов для каждого узла

Question

Учитывая дерево:

 
     F 
    / \ 
    C  E 
/\ /
A B D 

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

Answer 1

Если счетчик ребенок должен включать в себя внуков, сделать postorder обход, рекурсивно подсчета размеров ветвления в O (N):

int countChildren(Node node) { 
    int leftCount = node.left == null ? 0 : (countChildren(root.left) + 1); 
    int rightCount = node.right == null ? 0 : (countChildren(root.right) + 1); 

    int totalChildren = leftCount + rightCount; 

    System.out.println(node.name + ":" + totalChildren); 

    return totalChildren; 
}