完全二叉树的高度
完全二叉树是一种常见的二叉树结构，其中除了最后一层，每一层都被填满，最后一层从左向右填充节点。因此，在计算完全二叉树的高度时，我们只需要考虑它的最左边的路径（从根节点到最后一层的最左节点）即可。本文将从多个角度分析如何计算完全二叉树的高度。
基础概念
在开始分析完全二叉树的高度之前，我们首先需要了解完全二叉树的概念和性质。如前所述，完全二叉树是一种特殊的二叉树，其性质如下：
1. 深度为k的完全二叉树，节点数在2的k次方-1到2的k+1次方-1之间。
2. 若一节点在完全二叉树中的序号为i，则该节点的父节点的序号为i/2（向下取整），左子节点的序号为2i，右子节点的序号为2i+1。
3. 若完全二叉树的节点数为n，则其高度为log2(n+1)。
基于性质3，我们可以直接利用节点数来计算完全二叉树的高度。而且，由于完全二叉树的结构有一定的约束，其高度不会太深，因此使用此方法计算高度往往比较快捷。
递归计算
递归是计算二叉树高度的一种常用方法。对于普通二叉树，递归计算高度的代码如下所示：
```
int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
对于完全二叉树，我们可以根据其性质2来判断左右子树的高度，然后进行递归计算。
```
int getLeftDepth(TreeNode* root) {
int depth = 0;
while (root) {
depth++;
root = root->left;
}
return depth;
}
int getRightDepth(TreeNode* root) {
int depth = 0;
while (root) {
depth++;
root = root->right;
}
return depth;
}
int perfectBinaryTreeHeight(TreeNode* root) {
if (!root) return 0;
int leftDepth = getLeftDepth(root->left);
int rightDepth = getRightDepth(root->right);
if (leftDepth == rightDepth) {
return (1 << leftDepth) - 1;
} else {
return perfectBinaryTreeHeight(root->left) + 1;
}
}
```
以上代码中，getLeftDepth函数用于计算左子树的高度，getRightDepth函数用于计算右子树的高度。当左子树的高度等于右子树的高度时，说明整个树是满的，高度为2的k次方-1（即节点数-1）。否则，递归到左子树，继续计算高度即可。
迭代计算
除了递归，我们还可以使用迭代的方式计算完全二叉树的高度。我们可以通过队列来实现层序遍历，在遍历到每层的最后一个节点时，更新高度。
```
int perfectBinaryTreeHeight(TreeNode* root) {
if (!root) return 0;
queue
int height = 0;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
height++;
if (q.empty()) break;
}
return height;
}
```
以上代码中，我们依次遍历完全二叉树的每一层，并在最后一层时更新高度。遍历完成后，高度即为最后一层的层数。
结论与总结
本文介绍了三种计算完全二叉树高度的方法：基于节点数的公式、递归和迭代。其中，基于节点数的公式最为直接，递归和迭代则需要考虑完全二叉树的性质来进行计算。在实际应用中，我们可以根据场景的不同选择不同的计算方式。
