大可爱 发表于 2018-10-28 15:55:41

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

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

爱学习的懒懒君 发表于 2018-10-28 16:59:29

本帖最后由 爱学习的懒懒君 于 2018-10-28 17:06 编辑

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