求一个数组构成的二叉树的叶子节点的个数

假设数组为 arr，数组长度为 n。二叉树的叶子节点个数为数组中度为 0 的节点数。因此，我们需要先判断每个节点的度数，然后统计度数为 0 的节点数。

节点 i 的左子节点为 2*i+1，右子节点为 2*i+2。如果节点 i 的值为 -1，表示该节点不存在，即该节点的度数为 0。因此，我们可以遍历数组，判断每个节点的值是否为 -1，如果是，则该节点的度数为 0，统计变量 count 加 1。

以下是 Python 代码实现：

def count_leaf_nodes(arr, n):
    count = 0
    for i in range(n):
        if arr[i] == -1:
            count += 1
    return count

示例：

arr = [1, 2, 3, -1, 4, -1, 5]
n = len(arr)
count = count_leaf_nodes(arr, n)
print(count)  # 输出 3，即叶子节点个数为 3

在这个示例中，数组表示的二叉树如下：

        1
      /   \
     2     3
          /
         4
          \
           5

其中叶子节点为 2、4 和 5，共计 3 个。

相关问题

求一个数组构成的二叉树的叶子节点的个数c++完整代码

好的，以下是求一个数组构成的二叉树的叶子节点个数的 C++ 完整代码：

#include <iostream>
#include <vector>

using namespace std;

int count_leaf_nodes(vector<int>& arr) {
    int count = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == -1) {
            count++;
        }
    }
    return count;
}

int main() {
    vector<int> arr{1, 2, 3, -1, 4, -1, 5};
    int count = count_leaf_nodes(arr);
    cout << "叶子节点个数为：" << count << endl;
    return 0;
}

这个程序定义了一个 `count_leaf_nodes` 函数，它的参数是一个 vector<int> 类型的数组，返回值是叶子节点的个数。函数的实现和之前我给出的 Python 代码一样。主函数中定义了一个数组 `arr`，将它作为参数传递给 `count_leaf_nodes` 函数，并将返回值输出。

顺序存储 二叉树叶子节点数

顺序存储是指将数据元素按照线性顺序依次存放在一段物理地址连续的存储单元中，也称作数组存储。

二叉树叶子节点数指的是二叉树中没有子节点的节点数。在一棵二叉树中，叶子节点是指没有子节点的节点，也称作终端节点。

如果我们使用顺序存储来表示一棵二叉树，那么二叉树的节点可以按照层次遍历的顺序依次存放在一个数组中，其中二叉树的根节点存放在数组的第一个元素，它的左子节点存放在数组的第二个元素，右子节点存放在数组的第三个元素，以此类推。

对于一棵有n个节点的二叉树，它的叶子节点数可以通过遍历整个数组来计算。假设二叉树的节点存储在一个长度为n的数组中，我们可以遍历数组中的每个元素，如果该元素没有左子节点和右子节点，那么它就是一个叶子节点，统计叶子节点的个数即可。时间复杂度为O(n)。