Algorithm —— 已知一棵完全二叉树的节点数n，求叶节点数
·
题目如题，假设完全二叉树中，度为0的节点（即叶节点）数目为 n0n_0n0 ,度为1的节点数为 n1n_1n1,度为2的数目为 n2n_2n2，总数为 nnn
首先，我们得知道两个公式
(1)结点总数满足：
n=n0+n1+n2n = n_0 + n_1 + n_2n=n0+n1+n2
(2)出度与入度，也即分支数，满足：
n−1=0⋅n0+1⋅n1+2⋅n2n - 1 = 0·n_0 + 1·n_1 + 2·n_2n−1=0⋅n0+1⋅n1+2⋅n2
根据(1),(2)(1),(2)(1),(2)可得n0=n2+1=n−1−n12+1n_0 = n_2 + 1 = \frac{n-1 - n_1}{2} + 1n0=n2+1=2n−1−n1+1，但我们还是不能求出叶子节点数，我们还少了条件：
- 如果节点总数是偶数，则n1=1n_1 = 1n1=1
- 如果节点总数是奇数，则n1=0n_1 = 0n1=0
由此则有：n0=n−1−(n+1)%22+1n_0 = \frac{n-1 - (n+1) \% 2}{2} + 1n0=2n−1−(n+1)%2+1，若我们假设n=2019n = 2019n=2019，则有n0=(2019−1)−(2019+1)%22+1=1010n_0 = \frac{(2019-1) - (2019+1)\%2}{2} + 1= 1010n0=2(2019−1)−(2019+1)%2+1=1010
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
36
0- 0
已为社区贡献4条内容
所有评论(0)