求叶子节点的个数
N 叉树的每个节点有 N 个子节点。如果树有M个非叶子节点，如何找到叶子节点的数量？
An N-ary tree has N sub-nodes for each node. If the tree has M non-leaf nodes, How to find the no of leaf nodes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先，如果根是
0层，那么树的第K层将有N^K个节点。您可以开始逐级递增计数器，直到获得M个节点。这样你就可以知道树由多少层组成。叶子节点的数量是最后一层的节点数量 - 它是N^lastLevel。下面是一个示例：
N = 3，M = 4。所以我们发现树有两层（从0开始计数）。
答案是
3^2 = 9。注意：您也可以直接找到级别编号，注意
M是几何级数的总和：1 + 3 + 9 + 27 ... = M希望如此很清楚。
First of all if the root is level
0, then theK-th level of the tree will haveN^Knodes. You can start incrementing a counter level by level until you getMnodes. This way you will find how many levels is the tree consisting of. And the number of leaf nodes is the number of nodes on the last level - it isN^lastLevel.Here is an example:
N = 3, M = 4.So we found that the tree has two levels(counting from 0).
The answer is
3^2 = 9.Note: You can find the level number also directly, by noticing that
Mis a sum of geometric progression:1 + 3 + 9 + 27 ... = MHope it is clear.
从数学上讲，节点以几何级数增加。
0 级 - 1
第一级 - n
第二级 - n ^2
第三级 - n ^ 3
....
第 m 层 - n ^ m
因此，第 m-1 层的节点总数为 1 + n + n^2 + .. + n ^ m-1。
现在有一个很好的公式来计算 1 + a + a^2 + a^3 + ... + a^m ，即
(1 - n^(m+1))/(1-n)，我们称这个数量为K。
现在我们需要的是叶子节点的数量，即n ^ m，我们得到的是K。即总数非叶节点。做一些数学公式调整你会发现
n ^ m = K *(n-1) + 1.
例如，假设三叉树中非叶节点的总数为 40，那么使用此公式您可以得到叶子节点为 81，这是正确答案。
Mathematically speaking the nodes increase in the geometric progression.
0th level - 1
1st level - n
2nd level - n ^2
3rd level - n ^ 3
....
mth level - n ^ m
So the total number of nodes at m-1st level is 1 + n + n^2 + .. + n ^ m-1.
Now there is a good formula to calculate 1 + a + a^2 + a^3 + ... + a^m , which is
(1 - n^(m+1))/(1-n), lets call this quantity K.
Now what we need is the number of leaf nodes which is n ^ m, and what we have is K. i.e. total number of non-leaf nodes. Doing some mathematical formula adjustment you will find that
n ^ m = K *(n-1) + 1.
e.g. Lets say in 3-ary tree the total number of non-leaf nodes are 40, then using this formula you get the total number of leaf-nodes as 81 which is the right answer.