设一棵完全二叉树节点有699个，那么叶子结点多少个？

以下题是今天永辉超市笔试题原题

设一棵完全二叉树节点有699个，那么叶子结点多少个？

答：350个。

前提：

• 首先一棵完美二叉树高度为h，那么共有2^h-1个节点。第h层共有2^h-1个节点。
• 完全二叉树的特点：最后一层节点左边连续，倒数第二层节点右边连续（也就是倒数第二层节点是满的）。

• 因2¹⁰-1 > 699 > 2⁹-1，所以二叉树有10层；
• 又因前9层都是满的，所以前9层共有2⁹-1 = 511个；
• 所以最后一层有699 &＃8211; 511 = 188个节点；
• 所以第9层有子节点的节点数为188 / 2 = 94个；
• 又因第九层共有2^9-1 = 256个；
• 所以第九层的叶子结点数为256 &＃8211; 94 = 162个；
• 所以二叉树叶子结点共有188 + 162 = 350个。