バイナリ検索ツリーのノード数を計算する

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