data-structures - 查找叶节点数

Question

N-ary 树的每个节点有 N 个子节点。如果树有 M 个非叶子节点，如何找到叶子节点的数量？

Answer 1

首先，如果根是级别 0 ，然后是 K树的第 -th 级将有 N^K节点。您可以开始逐级递增计数器，直到获得 M节点。通过这种方式，您将找到树由多少个级别组成。叶子节点的数量是最后一层的节点数量 - 它是 N^lastLevel .

这是一个例子:N = 3, M = 4 .

First level = 3^0 = 1
Second level = 3^1 = 3
1 + 3 = 4

所以我们发现这棵树有两层(从0开始计数)。
答案是 3^2 = 9 .

注意:您也可以直接找到级别编号，注意 M是等比级数的和: 1 + 3 + 9 + 27 ... = M
希望它很清楚。