假设二叉树中的每个结点值为单个字符，采用顺序存储结构存储。设计一个算法，求二叉树t中的叶子结点个数。

可以遍历整棵树，对于每个结点，判断其是否为叶子结点，如果是则计数器加1。具体实现如下：

int countLeafNodes(char tree[], int root) {
    if (root == -1) {
        return 0;
    }
    if (tree[root] != '#') {  // 如果该结点不为空
        if (tree[2*root+1] == '#' && tree[2*root+2] == '#') {  // 如果该结点是叶子结点
            return 1;
        } else {  // 如果该结点不是叶子结点
            return countLeafNodes(tree, 2*root+1) + countLeafNodes(tree, 2*root+2);
        }
    } else {  // 如果该结点为空
        return 0;
    }
}

其中，`tree` 为存储二叉树的数组，`root` 为当前结点的下标。如果当前结点为空，则返回0；如果当前结点不为空，则判断其是否为叶子结点，是则返回1，否则递归遍历左右子树，并返回其叶子结点个数之和。

相关问题

假设二叉树中每个结点值为单个字符，采用顺序存储结构存储。设计一个算法， 求二叉树 t 中的叶子结点个数。

假设二叉树的顺序存储结构为一个一维数组，按照从上到下、从左到右的顺序存储二叉树中的所有结点。则二叉树的叶子结点必然出现在数组的后半部分，且后半部分中的结点没有子节点。

因此，可以从数组的中间位置开始，向后遍历数组，统计出叶子结点的个数。具体算法如下：

1. 定义变量count，表示叶子结点的个数，初值为0。
2. 定义变量mid，表示数组中间位置的下标，初值为数组长度除以2。
3. 从mid开始向数组末尾遍历，如果当前结点没有左右子节点，则count加1。
4. 如果当前结点有左右子节点，则将左子节点的下标设为mid*2，右子节点的下标设为mid*2+1，并将mid更新为左子节点的下标。
5. 重复步骤3和步骤4，直到遍历到数组末尾。

最终，count即为二叉树t中叶子结点的个数。

代码实现如下：

int countLeafNodes(char tree[], int len) {
    int count = 0;
    int mid = len / 2;
    for (int i = mid; i < len; i++) {
        if (tree[i] != '\0' && tree[i * 2] == '\0' && tree[i * 2 + 1] == '\0') {
            count++;
        } else {
            mid = i * 2;
        }
    }
    return count;
}

假设二叉树的每个结点值为单个字符，采用顺序存储结构存储。设计一个算法，求二叉树t中的叶子结点个数

对于顺序存储的二叉树，可以按照完全二叉树的方式进行存储，即将所有结点从上到下、从左到右依次存储在一个一维数组中，如果一个结点的下标为i，则其左孩子的下标为2i，右孩子的下标为2i+1。如果某个结点的下标超出了数组范围，则说明该结点不存在。根据这种存储方式，可以设计以下算法求二叉树t中的叶子结点个数：

1. 初始化叶子结点个数leaf为0；
2. 从根结点开始，按照顺序遍历数组中的每个结点，如果该结点存在且没有左右孩子，则leaf加1；
3. 遍历完所有结点后，leaf即为叶子结点个数。

具体实现如下（假设二叉树存储在数组a中，根结点下标为1，n为数组长度）：

def count_leaves(a, n):
    leaf = 0
    for i in range(1, n):
        if a[i] is not None and (2*i >= n or a[2*i] is None) and (2*i+1 >= n or a[2*i+1] is None):
            leaf += 1
    return leaf

该算法时间复杂度为O(n)，空间复杂度为O(1)。