Recursive Binary Decision-Tree Evaluator

二叉决策树是随机森林、梯度提升树（XGBoost、LightGBM、CatBoost）以及任何"若此特征 ≤ 该阈值则……"规则手册背后的标准推断结构。给定一行的特征向量，你从根开始走树：每个内部节点用一个特征跟一个阈值比较一下决定向左还是向右，到了叶子就读出预测值。求值过程是教科书级递归 DFS——从根到叶恰好一条路径，深度有界，没有回溯。

实现 solution(tree: dict, features: dict) -> float。树用嵌套 dict 编码，两种节点形状：

• 叶子：{"is_leaf": True, "value": <float>} —— 直接返回 value。
• 内部：{"is_leaf": False, "feature": <str>, "threshold": <float>, "left": <subtree>, "right": <subtree>} —— 取 features[feature]。若 features[feature] <= threshold 递归 left，否则递归 right。等号（精确相等）走左。

返回最终走到的那个叶子的 value。若树 malformed（节点缺 is_leaf、叶子缺 value、内部节点缺 feature / threshold / left / right 中任何一个），输入非法 → 应抛 ValueError。若走到的内部节点的 feature 不在 features 中，输入也非法 → 应抛 ValueError。本题在批量打分环境下把这两条错误路径都编码为哨兵返回值 -1.0（原始 spec 是抛 ValueError，-1.0 是为了兼容批量打分基础设施，沿用 coding-iv-put-bisection 的约定）。

示例

1. 单叶子。 solution({"is_leaf": True, "value": 3.5}, {}) 返回 3.5。根本身就是叶子，与 features 无关。

2. 两层树。 tree = {"is_leaf": False, "feature": "x", "threshold": 0.0, "left": {"is_leaf": True, "value": -1.0}, "right": {"is_leaf": True, "value": 1.0}}。当 features = {"x": -0.5} 时，−0.5 <= 0.0 走左 → 叶子 -1.0；当 features = {"x": 0.7} 时，0.7 > 0.0 走右 → 叶子 1.0。

3. 更深的递归树。 tree = {"is_leaf": False, "feature": "age", "threshold": 30.0, "left": {"is_leaf": False, "feature": "income", "threshold": 50.0, "left": {"is_leaf": True, "value": 0.1}, "right": {"is_leaf": True, "value": 0.4}}, "right": {"is_leaf": True, "value": 0.8}}。当 features = {"age": 25, "income": 80}：根处 25 <= 30 → 左；下一节点 80 > 50 → 右 → 叶子 0.4。当 features = {"age": 45}：根处 45 > 30 → 右 → 叶子 0.8（注意 income 根本没被查到）。

实战背景

这就是梯度提升树（gradient-boosted tree）模型的单行推断核心。线上服务时一个 XGBoost / LightGBM 模型动辄几百到几千棵树，给一行打分就是在每棵树上跑一遍这段递归遍历，再把所有叶子值加起来（再加 bias）。生产实现里会把递归拆成紧凑数组 (feature_id, threshold, left_idx, right_idx, value_if_leaf) 以便 cache 友好和 SIMD 批处理，但算法跟你这里要写的完全一样。对单行单树的递归走法熟练之后，再去碰特征归因（路径加权）、SHAP 值、模型导出 ONNX 之类的题目就只剩工程问题了。