c语言用两种递归办法求树的深度
时间: 2024-09-11 20:19:06 浏览: 22
在C语言中,我们可以使用递归方法来求解二叉树的深度,这里有两种常见的方式:
### 方法一:常规递归
```c
int maxDepth(struct TreeNode* root) {
if (root == NULL) { // 根节点为空,深度为0
return 0;
} else {
int leftDepth = maxDepth(root->left); // 左子树的深度
int rightDepth = maxDepth(root->right); // 右子树的深度
// 返回较大的一边的深度加1(表示当前节点所在层次)
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
}
```
### 方法二:优化递归(自底向上)
为了避免重复计算,我们可以在递归过程中保存已知深度的数据。这里可以借助辅助数组或栈来记录路径上的最大深度。
```c
int maxDepthHelper(struct TreeNode* root, int level, int* depth) {
if (root == NULL) {
*depth = level; // 如果遇到空节点,更新最大深度
return 0;
}
*depth = level; // 更新当前层的深度
int leftDepth = maxDepthHelper(root->left, level + 1, depth);
int rightDepth = maxDepthHelper(root->right, level + 1, depth);
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
int maxDepth(struct TreeNode* root) {
int depth = 0;
maxDepthHelper(root, 1, &depth);
return depth;
}
```
在这两种递归方法中,第一种直接递归求解,第二种则是通过存储中间结果优化递归效率。