R6-1 统计二叉树度为1的结点个数
时间: 2024-03-13 18:43:50 浏览: 16
一个二叉树的度为1的结点,指的是只有一个子节点的节点。统计二叉树度为1的结点个数可以通过递归实现。
具体思路如下:
1. 如果当前节点为空,则返回0。
2. 如果当前节点的左右子树都为空,则返回0。
3. 如果当前节点只有一个子节点,则返回1。
4. 如果当前节点有两个子节点,则递归地计算左右子树中度为1的节点个数之和。
下面是代码实现:
```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_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 0
if not root.left or not root.right:
return 1
return count_degree_one_nodes(root.left) + count_degree_one_nodes(root.right)
```
其中,TreeNode 是二叉树的结点类,count_degree_one_nodes 是统计二叉树度为1的节点个数的函数。
相关问题
统计二叉树度为1的结点个数C语言
以下是统计二叉树度为1的结点个数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点类型定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 统计二叉树度为1的结点个数
int countDegreeOne(TreeNode *root) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->left != NULL && root->right == NULL) {
count++;
}
if (root->left == NULL && root->right != NULL) {
count++;
}
count += countDegreeOne(root->left);
count += countDegreeOne(root->right);
return count;
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
TreeNode *node1 = (TreeNode *)malloc(sizeof(TreeNode));
node1->val = 2;
TreeNode *node2 = (TreeNode *)malloc(sizeof(TreeNode));
node2->val = 3;
TreeNode *node3 = (TreeNode *)malloc(sizeof(TreeNode));
node3->val = 4;
TreeNode *node4 = (TreeNode *)malloc(sizeof(TreeNode));
node4->val = 5;
root->left = node1;
root->right = node2;
node1->left = node3;
node2->left = node4;
// 统计二叉树度为1的结点个数并输出
int count = countDegreeOne(root);
printf("Degree 1 node count: %d\n", count);
return 0;
}
```
以上代码中,`countDegreeOne`函数接收一个二叉树的根节点指针,返回二叉树度为1的结点个数。在函数中,通过递归遍历二叉树,对于每个结点,判断其左右子树是否为空,若其中一个为空,则该结点度为1,统计个数并递归遍历其左右子树。最后返回统计结果即可。在`main`函数中,我构造了一个简单的二叉树,并调用`countDegreeOne`函数统计度为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的节点数量。