Подсчет левых дочерних узлов в дереве

Question

Я должен реализовать рекурсивный метод, который подсчитывает количество левых дочерних узлов дерева. Мой код на данный момент:

private int countLeftNodes(IntTreeNode node){
    int c = 0;
    if (node != null){
        c = 1 + countLeftNodes(node.left);
        countLeftNodes(node.right);
    }

    return c;
}

Возвращает число намного меньшее, чем должно быть. У меня ощущение, что мой обход отключен, потому что он, кажется, считает только самые левые дочерние узлы, а затем завершается. Когда я вызываю этот метод в IntTree размера 16, я должен получить 8 левых дочерних узлов, 7 правых дочерних узлов и один корень, но вместо этого я получаю 4 левых дочерних узла.

Answer 1

Вы никогда не считаете левые узлы в правом дереве.

private int countLeftNodes(IntTreeNode node)
{
    int c = 0;
    if (node.left != null)
    {
        c += 1 + countLeftNodes(node.left);
    }
    if(node.right != null)
    {
        c += countLeftNodes(node.right);
    }

    return c;
}

Answer 2

Для подсчета левых дочерних узлов вы можете сделать:

private int countLeftNodes(IntTreeNode node) {

    // no tree no left-child nodes      
    if(node == null) {
       return 0;
    }

    // left-child count of current node.
    int c = 0;

    // does the current node have a left-child ?
    if (node.left != null){
      c = 1;
    }

    // return left-child count of current node +
    // left-child count of left and right subtrees
    return c + countLeftNodes(node.left) + countLeftNodes(node.right);
}

Answer 3

Мой любимый стиль при использовании рекурсии - использовать какую-то функцию-оболочку, где основной метод вызывает другой, выполняющий грубую работу:

private int countLeftNodes(IntTreeNode node){
   int totalCount = reallyCountLeftNodes(IntTreeNode node, 0); 
   return totalCount;
}

private int reallyCountLeftNodes(IntTreeNode n, Int sum){
    if (n.left == NULL && n.right == NULL){  //check if we've hit rock bottom
        return sum;
    } else if (n.left == NULL) { //if the node's left is nil, go right
        reallyCountLeftNodes(n.right, sum++);   
    } else {
        reallyCountLeftNodes(n.left, sum++);  // Going as far left as possible!
    }
}

Обратите внимание, как основная функция вызывает другую. Я нахожу этот стиль чище и проще для понимания. Кроме того, вторая функция имеет переменную count для использования.

Answer 4

самое простое место для проверки, которое есть у родителя.

private int countLeftNodes(IntTreeNode node){

    int c = 0;
    if(node.left != null)
    {
        c++; 
        c+= countLeftNodes(node.left)
    }
    if(node.right != null)
    {
        c+= countLeftNodes(node.right);
    }

    return c;
}

Answer 5

private int countLeftNodes(IntTreeNode node){
    int c = 0;
    if (node != null){
        if(node.left!=null) {
           c = 1 + countLeftNodes(node.left);
        }
        if(node.right!=null){
            c +=countLeftNodes(node.right);
        }
    }

    return c;
}