统计树的叶子节点个数
时间: 2023-11-15 14:03:31 浏览: 72
统计树的叶子节点个数是树的基本问题之一。叶子节点是指没有子节点的节点,因此统计叶子节点的个数就是统计树中没有子节点的节点的个数。可以通过遍历树的方式来统计叶子节点的个数,具体方法如下:
1. 如果当前节点为空,则返回0。
2. 如果当前节点没有子节点,则返回1。
3. 如果当前节点有子节点,则递归遍历每个子节点,并将它们的叶子节点个数相加,最后返回总的叶子节点个数。
例如,对于一棵二叉树,可以使用以下代码来统计叶子节点的个数:
```
int countLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
```
相关问题
统计二叉树叶子结点个数
统计二叉树叶子结点个数的方法是通过递归实现的。具体步骤如下:
1. 如果当前节点为空,则返回0。
2. 如果当前节点没有左右子节点,则返回1。
3. 否则,递归计算左子树和右子树的叶子结点个数,并将它们相加。
以下是示例代码:
```
int countLeafNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
```
6-3 统计二叉树叶子结点个数
题目要求实现一个函数,统计二叉树的叶子结点个数。具体实现方法是遍历二叉树,对于每个节点,如果它是叶子节点,则计数器加1,否则递归遍历它的左右子树。最后返回计数器的值即可。
以下是参考代码:
```c
int LeafCount(BiTree T) {
int cnt = 0;
if (T != NULL) {
cnt += LeafCount(T->lchild); // 左子树的叶子节点个数
cnt += LeafCount(T->rchild); // 右子树的叶子节点个数
if (T->lchild == NULL && T->rchild == NULL) // 如果是叶子节点
cnt++; // 那么就自加一
}
return cnt;
}
```