[已解决]完全二叉树,叶节点为k,最下面一层的节点数目大于1，问树的深度

大可爱

完全二叉树，叶节点为k,最下面一层的节点数目大于1，问树的深度。
大佬，如何解答。

最佳答案

月排行榜 / 总排行榜

爱学习的懒懒君

2018-10-28 16:59:29

对于一个完全二叉树，叶节点分布在其倒数一二层
n层的完全二叉树，最少有2^(n - 2)个叶节点（最下面一层只有一个最左侧叶节点），题上要求最下面一层大于1就是最少2^(n - 2) + 1个
最多有2^(n - 1) - 1个叶节点（比n层二叉树少最右边一个叶节点）
所以看k落在哪个范围就可以求出n了

跳转到最佳答案楼层

爱学习的懒懒君

对于一个完全二叉树，叶节点分布在其倒数一二层
n层的完全二叉树，最少有2^(n - 2)个叶节点（最下面一层只有一个最左侧叶节点），题上要求最下面一层大于1就是最少2^(n - 2) + 1个
最多有2^(n - 1) - 1个叶节点（比n层二叉树少最右边一个叶节点）
所以看k落在哪个范围就可以求出n了