Numero di conteggi di nodi di sinistra in BST

Question

Dato un BST, sono obbligato a trovare il numero di nodi di sinistra dell'albero.

Esempio: `

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

La risposta dovrebbe essere 4, come (5, 1, 4, 7) sono tutti i nodi sinistra dell'albero.

Quello che sto pensando di fare è:

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; 
} 

So che è sbagliato, ma io non so perché. Qualcuno potrebbe spiegare perché, e anche aiutarmi con la risposta.

Answer 1

Il secondo ramo di ricorsione sovrascrive il valore dal primo. Inoltre dovresti aggiungere 1 per la radice sinistra.

Qualcosa di simile:

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

Nella seconda riga qui

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

si scarta il valore precedente di conteggio. Forse dovrebbe essere += anziché =.

Vorrei però esprimere in questo modo:

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

Answer 3

io penso che si debba ristrutturare il codice un po '. Invece di passare il conteggio corrente per i nodi di sinistra, basta riceverlo dai due bambini e aggiungerli.

Answer 4

Non è necessario propagare un accumulatore (il parametro count) lungo lo stack di chiamate, poiché non si sta facendo affidamento sulla ricorsione in coda.

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

Penso che la soluzione più elegante sia questa. Sì, certo che sono di parte. Sono :-) umana

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

total = countLeft (root, 0) 

Passando verso il basso l'indicatore per i nodi di sinistra, che semplifica ciò che deve essere passato su. Lo schema seguente mostra ogni somma passata: si inizia dal fondo e ogni null passa 0. 0.

Ogni nodo a sinistra passa a 1 più quello proveniente da entrambi i rami sottostanti. Ogni nodo a destra passa a 0 più quello che proviene da entrambi i rami sottostanti.

La radice non aggiunge nulla poiché non è né un nodo sinistro né uno destro (è trattato allo stesso modo di quello giusto).

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

---

Si può vedere il funzionamento di questo programma 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; 
} 

che emette le linee di debug:

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 versione non debug della funzione countLeft è semplice come lo pseudo-codice all'inizio di questa risposta:

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