编写一段代码,将二叉链表视为森林的孩子兄弟链表,计算森林中叶子个数。
时间: 2023-07-11 12:43:34 浏览: 89
假设二叉链表的节点结构如下:
```C++
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
```
可以使用以下代码计算森林中的叶子节点个数:
```C++
int countLeaves(TreeNode* forest) {
if (forest == nullptr) {
// 如果当前树为空,则返回0
return 0;
} else if (forest->left == nullptr && forest->right == nullptr) {
// 如果当前树只有一个节点,且为叶子节点,则返回1
return 1;
} else if (forest->left == nullptr) {
// 如果当前树只有一个节点,且为非叶子节点,则返回右子树中叶子节点的个数
return countLeaves(forest->right);
} else if (forest->right == nullptr) {
// 如果当前树只有一个节点,且为非叶子节点,则返回左子树中叶子节点的个数
return countLeaves(forest->left);
} else {
// 如果当前树有左子树和右子树,递归计算左子树和右兄弟树中叶子节点的个数
return countLeaves(forest->left) + countLeaves(forest->right);
}
}
int countLeavesInForest(TreeNode* forest) {
int count = 0;
while (forest != nullptr) {
// 遍历森林中的每个树,将每个树的叶子节点个数相加
count += countLeaves(forest);
forest = forest->right;
}
return count;
}
```
其中 `countLeaves` 函数用于计算单棵树中的叶子节点个数,`countLeavesInForest` 函数用于计算整个森林中的叶子节点个数。
阅读全文