在一棵二叉树中,求以值为X的结点为根结点的子树的深度
时间: 2024-03-12 14:46:33 浏览: 18
求以值为X的结点为根结点的子树的深度,可以通过递归实现。具体实现步骤如下:
1. 如果当前结点为NULL,返回0;
2. 如果当前结点的值为X,返回以该结点为根结点的子树的深度;
3. 否则,分别递归遍历当前结点的左子树和右子树,找到值为X的结点;
4. 如果左子树中找到了值为X的结点,返回左子树中以该结点为根结点的子树的深度;
5. 如果右子树中找到了值为X的结点,返回右子树中以该结点为根结点的子树的深度;
6. 如果左右子树都没找到值为X的结点,返回0。
代码实现如下:
```
int subtreeDepth(TreeNode* root, int X) {
if(root == NULL) {
return 0;
}
if(root->val == X) {
return maxDepth(root);
}
int leftDepth = subtreeDepth(root->left, X);
if(leftDepth > 0) {
return leftDepth;
}
int rightDepth = subtreeDepth(root->right, X);
if(rightDepth > 0) {
return rightDepth;
}
return 0;
}
int maxDepth(TreeNode* root) {
if(root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
其中,maxDepth函数用于求以当前结点为根结点的子树的深度。