统计二叉树中度为1
时间: 2024-01-23 19:09:20 浏览: 29
统计二叉树中度为1的节点数,可以通过遍历二叉树的方式进行统计。具体实现可以采用递归的方式,对每个节点进行判断,如果该节点的度为1,则计数器加1,并递归遍历其非空子节点。
以下是一个示例的 Python 代码实现:
``` python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_degree_one(root):
if not root:
return 0
count = 0
if (root.left and not root.right) or (root.right and not root.left):
count += 1
count += count_degree_one(root.left)
count += count_degree_one(root.right)
return count
```
其中,TreeNode 是一个二叉树节点的类,count_degree_one 是统计度为1的节点数的函数。在函数中,首先进行空节点的判断,然后判断当前节点的度是否为1,如果是,则计数器加1。最后递归遍历左右子节点,并将其子节点的度为1的节点数加到计数器中。
相关问题
统计二叉树中度为1结点个数c++
可以使用递归的方式来统计二叉树中度为1的节点数量。首先,我们需要定义二叉树的数据结构:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
然后,我们可以使用一个递归函数来统计二叉树中度为1的节点数量:
```cpp
int countDegreeOneNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
int count = 0;
// 如果当前节点的度为1,则count加1
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
count++;
}
// 递归统计左子树和右子树中度为1的节点数量
count += countDegreeOneNodes(root->left);
count += countDegreeOneNodes(root->right);
return count;
}
```
通过调用 `countDegreeOneNodes` 函数并传入二叉树的根节点,即可得到度为1的节点数量。
统计二叉树中度为1度结点个数
在一棵二叉树中,度为1的节点有两种情况:左子树为空或右子树为空。因此,我们可以通过遍历二叉树,统计左子树为空或右子树为空的节点个数来得到度为1的节点个数。
具体实现方法可以使用递归。对于一个节点,如果其左子树为空或右子树为空,则该节点的度为1;否则,将其左子树和右子树分别递归处理,最终将所有子树的度为1的节点个数加起来即为整棵树的度为1的节点个数。
以下是一个示例的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_degree_one_nodes(root):
if not root:
return 0
count = 0
if (not root.left and root.right) or (root.left and not root.right):
count = 1
count += count_degree_one_nodes(root.left) + count_degree_one_nodes(root.right)
return count
```
其中,`TreeNode` 表示二叉树的节点,`count_degree_one_nodes` 函数接收树的根节点作为参数,并返回度为1的节点个数。在函数中,如果当前节点的左子树为空或右子树为空,则将 `count` 计数器加1,然后递归处理其左子树和右子树,并将结果相加。最终,函数返回计数器的值,即为度为1的节点个数。