1. 理解问题
我们需要设计一个算法来计算给定二叉树的高度。二叉树的高度是指从根节点到最远叶子节点的最长路径上的节点数。如果树为空，则高度为 0；如果只有根节点，则高度为 1。
示例：
假设我们有如下的二叉树：
5
/ \
3 7
/ \ / \
2 4 6 8
这棵树的高度为 3，因为从根节点 5 到叶子节点（如 2 或 4）的最长路径包含 3 个节点（5 → 3 → 2）。
2. 输入输出
输入：
root：指向二叉树根节点的指针，表示二叉树的起始节点。
输出：
- 返回值：返回二叉树的高度。
3. 二叉树结构
二叉树节点的定义如下：
struct TreeNode {
int data; // 节点的值
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
4. 制定策略
为实现计算二叉树高度的算法，我们可以使用递归方式遍历树。在遍历过程中，计算左子树和右子树的高度，取较大值并加 1 作为当前节点的高度。
关键步骤：
- 递归遍历：从根节点开始递归遍历二叉树，计算左右子树的高度。
- 返回高度：返回左右子树高度的最大值加 1。
5. 实现代码
5.1 关键函数实现
// 查找二叉树的高度
int calculateHeight(struct TreeNode* root) {
// 如果树为空，返回 0
if (root == NULL) return 0;
// 递归计算左子树和右子树的高度
int leftHeight = calculateHeight(root->left);
int rightHeight = calculateHeight(root->right);
// 返回较大值加 1
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
5.2 完整 C 代码
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
struct TreeNode {
int data; // 节点的数据
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
// 创建一个新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 分配内存给新节点
newNode->data = data; // 设置节点的数据
newNode->left = NULL; // 初始化左子节点为 NULL
newNode->right = NULL; // 初始化右子节点为 NULL
return newNode; // 返回新节点
}
// 查找二叉树的高度
int calculateHeight(struct TreeNode* root) {
if (root == NULL) return 0;
int leftHeight = calculateHeight(root->left);
int rightHeight = calculateHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 主函数
int main() {
// 创建二叉树的节点
struct TreeNode* root = createNode(5);
root->left = createNode(3);
root->right = createNode(7);
root->left->left = createNode(2);
root->left->right = createNode(4);
root->right->left = createNode(6);
root->right->right = createNode(8);
// 计算二叉树的高度
int height = calculateHeight(root);
printf("二叉树的高度是: %d\n", height);
return 0;
}
5.3 代码说明
calculateHeight(struct TreeNode* root)：计算二叉树的高度。
- 如果当前节点为空，返回 0。
- 递归计算左子树和右子树的高度。
- 返回较大值加 1。
6. 运行结果
对于上述示例，运行结果为：二叉树的高度是: 3。
7. 时间和空间复杂度分析
- 时间复杂度：O(n)，最坏情况下需要遍历所有节点。
- 空间复杂度：O(h)，递归调用栈的深度最多为树的高度 h。
8. 总结
通过递归遍历二叉树，可以有效地计算其高度。这种方法简单且易于理解，对于深度优先搜索等其他操作也具有一定的实用性。