ツリー内の2つのバージョンのカウントリーフ

Question

これらの2つのバージョンの違いは何ですか？

public static int countLeaves(IntTreeNode root) { 
    if (root == null) { 
     return 0; 
    } else 
     return 1 + countLeaves(root.left) + countLeaves(root.right); 
} 

public static int countLeaves(IntTreeNode root) { 
    if (root == null) { 
     return 0; 
    } else if (root.left == null && root.right == null) { 
     return 1; 
    } else 
     return countLeaves(root.left) + countLeaves(root.right); 
} 

インターネットで最初のバージョンを使用しているものは見つかりませんでした。 最初のバージョンは間違っていますか？

私は紙でそれらをトレースしようとしましたが、それらは同じようです。 しかし、私はちょうど確信したい。

Answer 1

最初はツリー内のすべてのノードをカウントするように見えますが、2番目のカウンタはすべてのリーフをカウントします。

確かに最初のものでは、有効なツリーがもうなくなったときに再帰が止まり（root == null）、常に現在のノードの1を追加することによって、再帰的に左右のツリーをチェックします。

2番目の値は、条件if (root.left == null && root.right == null)を使用してリーフをカウントします。

これは、リーフがnullroot.leftとnullroot.rightのノードとして識別されていると仮定しています。

Answer 2

最初のバージョンは葉を数えていません。ノードを数えています。

第2版は実際に葉を数えています。

これらの方法は、ない同じ結果を返し、ここでの例は次のとおり第1の方法は、図3（ノード数）が返され、このようなツリーの

root(5) 
    / \ 
leaf(3) leaf(7) 

2つ目は、2（番号が返され葉の）。