深度为k的完全二叉树最少的节点数！！！理解不到啊！求教！

Question

深度为k的完全二叉树最少的节点数！！！理解不到啊！求教！为什么是2的k-1 次方

Answer 1

完全二叉树的意思：每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。所以深度为k的完全二叉树，其节点最少的情况为最后一层只有最左边有一个叶节点，其余各层填满。这种情况下，总节点数为2^(k-1)-1 +1, 其中2^(k-1)-1为除最后一层外的节点总数。

另外，这种计算方法认为只包含一个根节点的二叉树深度为1，有些书认为这种树深度为零，答案也会不一样。