在一棵二叉树中,求以值为X的结点为根结点的子树的深度
时间: 2024-03-13 21:48:19 浏览: 15
可以通过递归遍历二叉树,在遍历过程中判断每个节点的值是否为X,如果是X,则递归求解其左子树和右子树的深度并返回较大的值加1即可。
具体的实现可以参考下面的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def subtree_depth(root: TreeNode, x: int) -> int:
if not root:
return 0
if root.val == x:
return max(depth(root.left), depth(root.right)) + 1
return subtree_depth(root.left, x) or subtree_depth(root.right, x)
def depth(root: TreeNode) -> int:
if not root:
return 0
return max(depth(root.left), depth(root.right)) + 1
```
其中,`subtree_depth`函数用于求以值为X的结点为根结点的子树的深度,`depth`函数用于求某个节点的深度。
相关问题
用c++在一棵二叉树中,求以值为X的结点为根结点的子树的深度
同样地,在C++中也可以通过递归遍历二叉树来求解以值为X的结点为根结点的子树的深度。以下是示例代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
// 定义二叉树结点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 求二叉树深度的函数
int depth(TreeNode *root) {
if (!root) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
return max(left, right) + 1;
}
// 求以值为x的结点为根结点的子树的深度
int subtreeDepth(TreeNode *root, int x) {
if (!root) {
return 0;
}
if (root->val == x) {
int left = depth(root->left);
int right = depth(root->right);
return max(left, right);
}
int left = subtreeDepth(root->left, x);
int right = subtreeDepth(root->right, x);
return max(left, right);
}
int main() {
// 构造一棵二叉树
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->right = new TreeNode(4);
// 求以值为3的结点为根结点的子树的深度
int x = 3;
int subDepth = subtreeDepth(root, x);
cout << "以值为" << x << "的结点为根结点的子树的深度为" << subDepth << endl;
// 释放内存
delete root->right->right;
delete root->right;
delete root->left;
delete root;
return 0;
}
```
注意,在C++中需要手动释放动态分配的内存,避免内存泄漏。
用c语言在一棵二叉树中,求以值为X的结点为根结点的子树的深度
同样地,在C语言中也可以通过递归遍历二叉树来求解以值为X的结点为根结点的子树的深度。以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 求二叉树深度的函数
int depth(TreeNode *root) {
if (!root) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
// 求以值为x的结点为根结点的子树的深度
int subtreeDepth(TreeNode *root, int x) {
if (!root) {
return 0;
}
if (root->val == x) {
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
int left = subtreeDepth(root->left, x);
int right = subtreeDepth(root->right, x);
return left > right ? left : right;
}
int main() {
// 构造一棵二叉树
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 4;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 求以值为3的结点为根结点的子树的深度
int x = 3;
int subDepth = subtreeDepth(root, x);
printf("以值为%d的结点为根结点的子树的深度为%d\n", x, subDepth);
// 释放内存
free(root->right->right);
free(root->right);
free(root->left);
free(root);
return 0;
}
```
注意,在C语言中需要手动释放动态分配的内存,避免内存泄漏。