算法设计题: 以二叉链表为存储结构,设计一个求二叉树叶子节点数的算法。
时间: 2024-11-22 22:34:49 浏览: 4
为了设计一个求解二叉链表中叶子节点数的算法,我们可以采用深度优先搜索(Depth-First Search,DFS)策略。以下是算法的大致步骤:
1. 定义一个辅助函数,用于递归检查当前节点是否是叶子节点:
- 如果当前节点为空,则返回0;
- 如果当前节点的左右孩子都为空,则返回1,表示当前节点是一个叶子节点;
- 否则,返回左右两个子节点的叶子节点数之和。
2. 主函数中初始化一个变量 `leaf_count` 为0,代表叶子节点总数。
- 选择二叉链表的根节点作为起点,调用辅助函数;
- 遍历整个二叉链表,每次递归调用,累加返回的叶子节点数。
下面是一个简单的C语言伪代码实现:
```c
typedef struct Node {
int val;
struct Node* left;
struct Node* right;
} TreeNode;
int countLeaves(TreeNode* root) {
if (root == NULL) return 0;
// 如果左孩子和右孩子都是空,那么当前节点就是一个叶子节点
if (root->left == NULL && root->right == NULL) {
return 1;
} else {
// 递归计数左子树和右子树的叶子节点
return countLeaves(root->left) + countLeaves(root->right);
}
}
```
阅读全文