题目重点：把二元特征/标签的树学习问题拆成不纯度、候选分裂、递归与过拟合控制。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练场景每行 d 个 {0,1} 特征，标签 {0,1}；每层只能按尚未使用的某个特征作 0/1 切分，目标先取 Gini gain 最大。
- 同 gain 按最小特征 ID，叶标签平票按 0；空数据不建节点。最大深度/最小叶样本数由调用者提供，题目未规定。
解题路线
- 在节点统计正负样本数，Gini=1−p₀²−p₁²；对每个可用特征划分左右子集，计算加权子 Gini，gain=父 Gini−子加权 Gini。选 gain 最大且有效分裂的特征。
- 纯标签、无可用特征、无正增益、深度上限或样本不足时生成叶，预测节点多数类；如果某候选特征的一侧为空，不应仍递归生成空树。
- 训练递归时把本节点样本索引分到两边，不反复复制整份特征矩阵；预测从根按每层特征值走到叶。
- 信息增益/entropy 也可，但若测试指定 Gini 不可混用。剪枝和 max_depth 可以限制过拟合，评估要按时间/用户或数据独立性切分，不能只报训练准确率。
手动走一遍
X 的第 0 特征完美区分标签时，根选特征 0、两个纯叶；若所有样本第 0 特征都为 1，按它分裂会有空分支，必须忽略该候选并试其他特征。
规模与取舍
N 样本、d 个二元特征、最大深度 H：朴素每层枚举特征与样本，最坏 O(NdH) 统计工作（实际由各层样本分配和剩余特征数决定），树/样本索引空间 O(N+d×节点数) 依实现。题目没有 N/d 范围。
易错点与追问
容易失分的边界
- 只按训练集准确率选 split，不处理同样好但复杂度不同的树。
- 空分支递归导致无定义叶。
- 标签纯净还继续分裂。
- 未定义 gain 平局与叶多数票平局。
- 在同一批数据上训练/评估并声称泛化好。
继续深挖
- Gini 与 entropy 何时选？
- 类别严重不平衡如何设停止/加权？
- 连续特征如何找阈值？
- 如何做后剪枝和交叉验证？
