怎么理解12个结点的平衡二叉树中叶子结点的最小层数为3，最大层数为5。最小层数为什么为3？

2024-12-01 13:22:16

推荐回答（1个）

回答1：

当层数最少的时候，你就把它当作是一个完全二叉树，依次排列12个结点。第一层1个，第二层2个，第三层4个，这里就7个结点了，第四层只要5个结点就够12个，这样画下来你会发现第三层和第四层都有叶子节点，最小层数就是3了。
当层数最多的时候，n 个结点的平衡二叉树的最大深度：log₂n + 1；所以这里是 log₂12 +1 向上取整数是 4+1=5。这是一棵任何左子树跟右子树的高度差（平衡因子）都是 1 或者 -1 的二叉树。