校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树相关概念
题目

某棵完全二叉树上有698个节点,则该二叉树的叶子节点数为

A.349

B.350

C.255

D.351

解答

正确答案是 A

首先明确完全二叉树的概念:
最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。
因为2^9 - 1 < 698 < 2^10 - 1,
所以共有10层,前九层的节点数为2^9 - 1 = 511,第十层为689 - 511 = 187。
187/2 = 93余1,所以第九层有93个度为2的节点,一个度为1的节点。

第九层叶节点为 256 - 94 = 162;
第十层叶节点为 187;
叶节点总数为 187 + 162 = 349.

C 0条回复 评论

帖子还没人回复快来抢沙发