用c++在一棵二叉树中,求以值为X的结点为根结点的子树的深度
时间: 2024-03-13 16:48:23 浏览: 20
同样地,在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++中需要手动释放动态分配的内存,避免内存泄漏。