Подсчет узлов в двоичном дереве поиска

Question

Я написал следующую рекурсивную функцию для подсчета всех узлов в двоичном дереве поиска.

class BST { 
........... 
int lc=0,rc=0; 
int totalnodes(Node root){ 
    if(root==null)return 0; 
    lc=totalnodes(root.left); 
    rc=totalnodes(root.right); 
    return rc+lc+1; 
    } 
} 

Приведенные выше результаты функции в неправильном answer.However, следующий код работает:

class BST { 
    int totalnodes(Node root){ 
     if(root==null)return 0;  
     return totalnodes(root.left)+totalnodes(root.right)+1; 
    } 
    } 

Что это такое, что мне не хватает с первой функцией.

Answer 1

Вам не хватает того, что ваши lc и rc не являются локальными. И, таким образом, после того, как lc был вычислен для узла root, он будет перезаписан вызовом totalnodes(root.left), тогда как вычисление результата для root состоится позднее.

Попробуйте переместить ваши lc, rc заявления к методу:

int totalnodes(Node root){ 
    if(root==null)return 0; 
    int lc=totalnodes(root.left); 
    int rc=totalnodes(root.right); 
    return rc+lc+1; 
}