Contar el número de nodos de la izquierda en BST

Question

Dado un BST, estoy obligado a encontrar el número de nodos de la izquierda del árbol.

Ejemplo: `

  +---+ 
      | 3 | 
      +---+ 
     / \ 
    +---+  +---+ 
    | 5 |  | 2 | 
    +---+  +---+ 
    /  / \ 
+---+  +---+  +---+ 
| 1 |  | 4 |  | 6 | 
+---+  +---+  +---+ 
     /
    +---+ 
    | 7 | 
    +---+` 

La respuesta debe ser de 4, como (5, 1, 4, 7) son todos los nodos izquierda del árbol.

Lo que estoy pensando en hacer es:

public int countLeftNodes() { 
    return countLeftNodes(overallRoot, 0); 
} 

private int countLeftNodes(IntTreeNode overallRoot, int count) { 
    if (overallRoot != null) { 
     count += countLeftNodes(overallRoot.left, count++);  
     count = countLeftNodes(overallRoot.right, count); 
    } 
    return count; 
} 

Sé que está mal, pero no sé qué. ¿Podría alguien explicar por qué, y también ayudarme con la respuesta?

Answer 1

La segunda rama de recursividad sobrescribe el valor de la primera. También debe agregar 1 para la raíz izquierda.

Algo así como:

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

    if (node.right != null) 
     count += countLeftNodes(node.right); 


    return count; 
} 

Answer 2

En su segunda línea aquí

count += countLeftNodes(overallRoot.left, count++);  
count = countLeftNodes(overallRoot.right, count); 

se descarta el valor anterior de recuento. Tal vez debería ser += en lugar de =.

Me obstante expresarlo así:

private int countLeftNodes(IntTreeNode root) { 
    return (root.left == null ? 0 : countLeftNodes(root.left) + 1) + 
      (root.right == null ? 0 : countLeftNodes(root.right)); 
} 

Answer 3

Yo creo que hay que reestructurar su código un poco. En lugar de pasar el recuento actual de los nodos izquierdos, solo recíbelo de los dos hijos y agréguelos.

Answer 4

No es necesario propagar un acumulador (el parámetro count) por la pila de llamadas, ya que no se basa en recursividad final.

public int countLeftNodes(IntTreeNode node) { 
    // This test is only needed if the root node can be null. 
    if (node == null) return 0; 

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

Answer 5

Creo que la solución más elegante es esta. Sí, por supuesto que soy parcial. Estoy :-) humana

def countLeft (node,ind): 
    if node == null: return 0 
    return ind + countLeft (node->left, 1) + countLeft (node->right, 0) 

total = countLeft (root, 0) 

Al pasar por el indicador de nodos de izquierda, que simplifica lo que tiene que pasar para arriba. El siguiente diagrama muestra cada suma que se pasa: comienza en la parte inferior y cada nulo pasa a 0.

Cada nodo de la izquierda pasa hacia arriba 1 más lo que provenga de las dos ramas a continuación. Cada nodo de la derecha pasa a 0 más lo que provenga de ambas ramas a continuación.

La raíz no agrega nada ya que no es un nodo izquierdo ni derecho (se trata igual que a la derecha).

     4 
         ^
         | 
         +---+ 
         | 3 | 
      __________+---+__________ 
      /2      2\ 
     +---+       +---+ 
     | 5 |       | 2 | 
     +---+       +---+ 
    /1        /2 0\ 
+---+       +---+  +---+ 
| 1 |       | 4 |  | 6 | 
+---+       +---+  +---+ 
/0 0\      /1 0\  /0 0\ 
          +---+ 
          | 7 | 
          +---+ 
         /0 0\ 

---

Se puede ver el funcionamiento de este programa completo:

#include <stdio.h> 

typedef struct sNode { int val; struct sNode *left, *right; } tNode; 

#define setNode(N,V,L,R) N.val = V; N.left = L; N.right = R 

int countLeft (tNode *node, int ind) { 
    if (node == NULL) return 0; 
    int x = ind + countLeft (node->left, 1) + countLeft (node->right, 0); 
    printf ("Node %d passing up %d\n", node->val, x); 
    return x; 
} 

int main (void) { 
    tNode n3, n5, n1, n2, n4, n6, n7; 
    setNode (n3, 3, &n5, &n2); 
    setNode (n5, 5, &n1, NULL); 
    setNode (n1, 1, NULL, NULL); 
    setNode (n2, 2, &n4, &n6); 
    setNode (n4, 4, &n7, NULL); 
    setNode (n7, 7, NULL, NULL); 
    setNode (n6, 6, NULL, NULL); 

    printf ("countLeft is %d\n", countLeft (&n3, 0)); 
    return 0; 
} 

que da salida a las líneas de depuración:

Node 1 passing up 1 
Node 5 passing up 2 
Node 7 passing up 1 
Node 4 passing up 2 
Node 6 passing up 0 
Node 2 passing up 2 
Node 3 passing up 4 
countLeft is 4 

La versión no depuración de la función countLeft es tan simple como el pseudo-código al comienzo de esta respuesta:

int countLeft (tNode *node, int ind) { 
    if (node == NULL) return 0; 
    return ind + countLeft (node->left, 1) + countLeft (node->right, 0); 
}