用c语言编写:在一棵二叉树中,求以值为X的结点为根结点的子树的深度
时间: 2024-03-14 07:43:22 浏览: 96
求二叉树的深度
可以通过递归的方式来求解以值为X的结点为根结点的子树的深度。
首先,需要定义一个二叉树的结构体:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
然后,可以编写一个递归函数来求解以值为X的结点为根结点的子树的深度:
```c
int subtreeDepth(TreeNode* root, int x) {
if (root == NULL) { // 如果根节点为空,返回0
return 0;
}
if (root->val == x) { // 如果根节点的值等于x,返回以它为根节点的子树的深度
return maxDepth(root);
}
// 否则,在左右子树中查找x
int leftDepth = subtreeDepth(root->left, x);
int rightDepth = subtreeDepth(root->right, x);
// 如果左右子树中都没有找到x,返回0
if (leftDepth == 0 && rightDepth == 0) {
return 0;
}
// 如果左右子树中有一个找到了x,返回找到的子树的深度
return leftDepth + rightDepth + 1;
}
```
其中,maxDepth函数用来求解以某个节点为根节点的子树的深度:
```c
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
这里用到了max和maxDepth两个函数,需要包含头文件:
```c
#include <stdio.h>
#include <stdlib.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
```
阅读全文