统计二叉树中只有左孩子的结点个数代码实现
时间: 2024-01-23 07:43:40 浏览: 25
可以使用递归实现统计二叉树中只有左孩子的结点个数。
具体实现方法如下:
1. 如果当前节点为空,返回0。
2. 如果当前节点只有左孩子,返回1加上递归调用左子树的结果。
3. 如果当前节点有左右孩子,返回递归调用左子树和右子树的结果之和。
代码实现如下所示:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_left_children(root):
if not root:
return 0
if root.left and not root.right:
return 1 + count_left_children(root.left)
else:
return count_left_children(root.left) + count_left_children(root.right)
```
其中,TreeNode 是定义二叉树节点的类,count_left_children 函数是统计二叉树中只有左孩子的结点个数的函数。函数中的 root 参数是二叉树的根节点。
相关问题
C语言实现统计二叉树中只有左孩子的结点个数问题
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct node {
int data;
struct node *left, *right;
} Node;
// 创建二叉树
Node* createTree() {
int val;
printf("请输入节点的值(-1表示结束):");
scanf("%d", &val);
if (val == -1) {
return NULL;
}
Node* root = (Node*)malloc(sizeof(Node));
root->data = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 统计只有左孩子的结点个数
int countOnlyLeft(Node* root) {
// 如果为空,返回0
if (root == NULL) {
return 0;
}
// 如果左子结点为空,且右子结点不为空,则该结点是只有左孩子的结点
if (root->left != NULL && root->right == NULL) {
return 1 + countOnlyLeft(root->left);
}
// 否则递归遍历左右子树
return countOnlyLeft(root->left) + countOnlyLeft(root->right);
}
int main() {
Node* root = createTree();
int count = countOnlyLeft(root);
printf("只有左孩子的结点个数为:%d\n", count);
return 0;
}
```
该程序中,首先通过 `createTree` 函数创建一棵二叉树。然后,通过 `countOnlyLeft` 函数统计只有左孩子的结点个数。具体实现过程如下:
- 如果当前结点为空,返回0。
- 如果当前结点的左子结点不为空且右子结点为空,则该结点是只有左孩子的结点,返回1加上遍历左子树的结果。
- 否则递归遍历左右子树,返回两个子树的结果之和。
最后,在 `main` 函数中调用 `countOnlyLeft` 函数统计只有左孩子的结点个数,并输出结果。
统计二叉树中只有左孩子的结点个数c语言
以下是统计二叉树中只有左孩子的结点个数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 统计二叉树中只有左孩子的结点个数
int countNodesWithOnlyLeftChild(TreeNode* root) {
if (!root) {
return 0;
}
int count = 0;
if (root->left && !root->right) {
count = 1;
}
return count + countNodesWithOnlyLeftChild(root->left) + countNodesWithOnlyLeftChild(root->right);
}
int main() {
// 构造一个二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 3;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 4;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
// 统计只有左孩子的节点个数
int count = countNodesWithOnlyLeftChild(root);
printf("二叉树中只有左孩子的结点个数为:%d\n", count);
// 释放内存
free(root->left->left);
free(root->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```
以上代码中,我们使用递归方式遍历二叉树,在每个结点处判断其是否只有左孩子,如果是则计数器加1,最终返回计数器的值。在main函数中,我们构造一个二叉树并调用函数进行统计,最后释放内存。