在二叉树中查找值为x并求出以该结点为根的子树深度
时间: 2023-06-17 16:03:47 浏览: 57
在二叉树中查找值为x的结点,可以采用递归的方式进行查找。首先判断当前结点是否为NULL,如果是,则返回NULL;否则,判断当前结点的值是否为x,如果是,则返回当前结点;否则,递归地在当前结点的左子树和右子树中查找值为x的结点。
以下是 C++ 代码实现:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* search(TreeNode* root, int x) {
if (root == NULL) {
return NULL;
}
if (root->val == x) {
return root;
}
TreeNode* left = search(root->left, x);
if (left != NULL) {
return left;
}
return search(root->right, x);
}
```
对于找到值为x的结点,可以使用递归求取以该结点为根的子树深度。子树深度可以通过左右子树的深度取最大值再加1得到。
以下是 C++ 代码实现:
```cpp
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_depth = depth(root->left);
int right_depth = depth(root->right);
return max(left_depth, right_depth) + 1;
}
int subtreeDepth(TreeNode* root, int x) {
TreeNode* node = search(root, x);
if (node == NULL) {
return 0;
}
return depth(node);
}
```
其中,depth函数用于求取二叉树的深度。subtreeDepth函数用于求取以值为x的结点为根的子树深度。