要求实现一个函数求二叉树中值为key 的结点个数
时间: 2024-02-18 12:00:43 浏览: 27
好的,针对你的要求,我可以给出以下的解法,采用递归的思路实现:
```c++
int count(TreeNode* root, int key) {
if (!root) {
return 0;
}
if (root->val == key) {
return 1 + count(root->left, key) + count(root->right, key);
} else {
return count(root->left, key) + count(root->right, key);
}
}
```
在上面的代码中,如果当前节点为空,则返回 0,否则判断当前节点的值与 key 是否相等,如果相等则返回 1 加上左右子树中值为 key 的节点数目,否则返回左右子树中值为 key 的节点数目之和。
最后,调用上述函数即可得到二叉树中值为 key 的节点数目。
相关问题
要求实现一个函数,求二叉树中值为 key 的节点个数(输入-1表示指针为 NULL)下图所示二叉树中值为1的结点个数为3 个
以下是求二叉树中值为 key 的节点个数的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_node(root, key):
if not root:
return 0
count = 0
if root.val == key:
count = 1
count += count_node(root.left, key)
count += count_node(root.right, key)
return count
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(1)
root.right.right = TreeNode(5)
print(count_node(root, 1)) # 输出 3
```
该函数的实现思路是递归地遍历二叉树,如果当前节点的值等于 key,则计数器 count 加1,然后递归遍历当前节点的左子树和右子树,将它们的计数器值累加到 count 中。最后返回 count 的值即可。
设计一个算法求二叉树中值为x的结点所在的层次。
可以使用递归遍历整个二叉树,在遍历每个结点时,比较该结点的值是否等于x,若等于则返回该结点所在的层次,否则继续遍历其左右子树。具体实现可以参考以下代码:
```
int findNodeLevel(TreeNode* root, int x, int level) {
if (root == nullptr) {
return 0;
}
if (root->val == x) {
return level;
}
int l = findNodeLevel(root->left, x, level + 1);
if (l != 0) {
return l;
}
return findNodeLevel(root->right, x, level + 1);
}
```
其中,参数root表示当前结点,x表示目标结点值,level表示当前结点的层次。递归的结束条件是当前结点为nullptr,即遍历到了叶子结点但仍然没找到目标结点,此时返回0表示未找到。若当前结点的值与目标结点值相等,直接返回当前层次level。否则继续遍历其左右子树,并将层次level加1传递给下一层递归。若左子树中找到目标结点,则返回左子树中的结果;否则返回右子树中的结果。