完全二叉树性质
链接：https://www.nowcoder.com/questionTerminal/4342cbc1732644dc84938543392c1b34?orderByHotValue=1&page=1&onlyReference=false
来源：牛客网
n0是度为1的节点个数，n1是度为1的节点个数，n2是度为2的节点个数【度 指的是：结点所拥有的子树的个数，叶子节点的度为0】
则总节点个数n=n0+n1+n2
在二叉树中，满足一个条件: 度为2的节点个数总比叶子节点个数少一个，即n2=n0-1
在完全二叉树中，又满足一个条件，总节点数为偶数时，度为1的节点数为1个；总节点数为奇数时，度为1的节点个数为0
本题中，总节点数为2018，是偶数，所以n1=1
将n2=n0-1代入n=n0+n1+n2中，可得n=2n0，则叶子节点数，也就是n0=n/2=1009,答案就出来了
同样的，当总节点数为奇数时，n1=0，n=n0+0+n0-1，即n=2n0-1，n0=(n+1)/2
所以，可以得出结论，具有n个节点的完全二叉树，其叶子节点个数为n0/2【n为偶数】或者(n+1)/2【n为奇数】
京公网安备 11010502036488号