Question

设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（ ）

Answer 1

设二叉树中度为0也就是叶子结点个数n0，度为1结点个数n1，度为2结点个数n2
于是n0 + n1 + n2 = 699
按照二叉树的性质n0 = n2 +1
于是2n2 +n1 + 1 = 699
考虑到完全二叉树中度为1结点个数最多1个，因此n1 = 0
n2 = 349
所以n0 = 350，即叶子结点350个

Answer 2

B：350
首先你得知道什么叫完全二叉树！
完全二叉树(Complete Binary Tree)
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
做这种题目你要知道二叉树的两个特点！第k层的节点个数最多2^(k-1)个，高度为k层的二叉树，最多2^k-1个节点！
则在本题目中，共699个节点，因为是完全二叉树，2^10-1>699>2^9-1，所以高度为10，可以确定1到9层全满，节点总算为511，剩下的188个肯定为叶子节点！第10层上的188个节点挂在第九层的188/2=94个节点上，则第九层剩下的2^（9-1）-94=162个也为叶子节点，最后总共188+162=350个叶子节点！