03-树2 list leaves (25 分)

题目描述

给定一个树，请你编写程序，计算其中所有叶子节点的个数。

输入格式:

输入第一行给出一个正整数 N（≤10^4），即树的节点数。随后 N−1 行给出了父节点的编号（从 1 开始编号，根节点的编号为 1），其余信息，格式如下：

父节点编号 子节点个数 子节点编号[1] 子节点编号[2] …… 子节点编号[子节点个数]

输出格式:

统计叶子节点的个数，并在一行中输出。

输入样例:

8
1 2 2 3
2 2 4 5
4 1 7
5 2 6 8

输出样例:

4

题目分析

这道题目是一道树的遍历问题，我们可以使用深度优先遍历或者广度优先遍历来解决。这里我们使用深度优先遍历来解决。

我们可以从根节点开始遍历，如果当前节点没有子节点，那么就是叶子节点，否则就递归遍历子节点，直到找到叶子节点。

代码实现

C++ 代码

相关问题

python 连续比较_python实现连续变量最优分箱详解--CART算法(2)

好的，关于Python实现连续变量最优分箱详解，我可以为您提供一些基础的思路和代码实现。该方法是基于CART算法实现的，具体如下：

首先，我们需要导入相关的库，包括numpy、pandas和sklearn等：

import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeRegressor

然后，我们需要定义一个函数来执行最优分箱操作，该函数的输入参数包括待分箱的数据、目标变量、最小样本数、最大分箱数、以及是否需要返回分箱结果等：

def binning_continuous_var(data, target, min_samples_leaf=50, max_bins=10, return_bins=False):
    # 将数据和目标变量拼接
    data = pd.concat([data, target], axis=1)
    # 获取连续变量的列名
    cont_cols = data.select_dtypes(include=[np.number]).columns.tolist()
    # 循环处理每个连续变量
    for col in cont_cols:
        # 对该变量进行分箱操作
        binned_col, bins = bin_continuous_var(data, col, target, min_samples_leaf, max_bins)
        # 将分箱结果更新到数据集中
        data[col] = binned_col
    # 如果需要返回分箱结果，则返回数据集和分箱边界值
    if return_bins:
        return data, bins
    # 否则，仅返回数据集
    else:
        return data

接下来，我们需要定义一个子函数来执行单个连续变量的分箱操作，该函数的输入参数包括待分箱的数据、连续变量的列名、目标变量、最小样本数和最大分箱数等：

def bin_continuous_var(data, col, target, min_samples_leaf, max_bins):
    # 获取该变量的取值范围
    data_range = data[col].max() - data[col].min()
    # 如果取值范围为0，则直接返回原始变量和一个空的分箱边界值列表
    if data_range == 0:
        return data[col], []
    # 否则，使用CART算法进行分箱操作
    else:
        # 初始化决策树模型
        tree_model = DecisionTreeRegressor(
            criterion='mse',
            min_samples_leaf=min_samples_leaf,
            max_leaf_nodes=max_bins,
            random_state=42
        )
        # 拟合决策树模型
        tree_model.fit(data[col].to_frame(), target)
        # 获取决策树的叶节点数目
        n_leaves = tree_model.get_n_leaves()
        # 如果叶节点数目大于等于最大分箱数，则需要重新设置最大叶节点数目并重新拟合模型
        while n_leaves >= max_bins:
            max_bins -= 1
            tree_model = DecisionTreeRegressor(
                criterion='mse',
                min_samples_leaf=min_samples_leaf,
                max_leaf_nodes=max_bins,
                random_state=42
            )
            tree_model.fit(data[col].to_frame(), target)
            n_leaves = tree_model.get_n_leaves()
        # 获取叶节点的取值范围
        leaves_range = [(tree_model.tree_.threshold[i - 1], tree_model.tree_.threshold[i]) for i in
                        np.where(tree_model.tree_.children_left == -1)[0]]
        # 初始化分箱边界值列表，将最小值和最大值作为边界值的起点和终点
        bins = [data[col].min()] + [i[1] for i in leaves_range[:-1]] + [data[col].max()]
        # 计算每个取值所对应的分箱编号
        binned_col = np.digitize(data[col], bins)
        # 将分箱编号转换为分箱中心点的取值
        binned_col = pd.Series(binned_col, index=data.index)
        binned_col = binned_col.map(lambda x: np.round(np.mean(data[target.name][binned_col == x]), 4))
        # 返回分箱结果和分箱边界值列表
        return binned_col, bins

最后，我们可以使用上述代码实现对连续变量的最优分箱操作，例如：

# 生成测试数据
data = pd.DataFrame({
    'col1': np.random.rand(1000),
    'col2': np.random.rand(1000),
    'col3': np.random.rand(1000),
    'target': np.random.randint(0, 2, 1000)
})
# 执行最优分箱操作
data_binned = binning_continuous_var(data.drop('target', axis=1), data['target'], min_samples_leaf=50, max_bins=10, return_bins=False)

以上就是Python实现连续变量最优分箱的基础思路和代码实现，希望可以对您有所帮助。

用递归算法遍历树，将树的最后一级取出组成新数组

假设树的节点结构如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

可以使用递归算法遍历树，将树的最后一级取出组成新数组。代码如下：

public int[] getLeaves(TreeNode root) {
    List<Integer> leaves = new ArrayList<>();
    getLeavesHelper(root, leaves);
    int[] result = new int[leaves.size()];
    for (int i = 0; i < leaves.size(); i++) {
        result[i] = leaves.get(i);
    }
    return result;
}

private void getLeavesHelper(TreeNode root, List<Integer> leaves) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        leaves.add(root.val);
    } else {
        getLeavesHelper(root.left, leaves);
        getLeavesHelper(root.right, leaves);
    }
}

首先定义一个空的列表 `leaves`，用于存储最后一级节点的值。然后调用递归辅助函数 `getLeavesHelper`，遍历树的所有节点。如果当前节点是叶子节点，则将其值添加到 `leaves` 列表中；否则，递归遍历当前节点的左子树和右子树。最后，将 `leaves` 列表转换为数组并返回。