Python递归列表拆分结果生成带0/1后缀的树形索引方法

原有拆分逻辑未携带节点索引信息，只需在递归拆分时传入当前节点对应的索引，拆分出左右子列表时直接生成子节点索引，即可一次性得到节点与索引的映射关系，无需二次遍历拆分结果。

实现代码 #

def split_with_index(class_names, current_idx, res_map):
    list_len = len(class_names)
    if list_len <= 1:
        return
    mid = list_len // 2
    left_part = class_names[:mid]
    right_part = class_names[mid:]
    # 存储当前拆分节点与对应索引，用不可变元组做key解决列表不可哈希问题
    current_split = [left_part, right_part]
    res_map[tuple(map(tuple, current_split))] = current_idx
    # 递归处理左子树，父索引末尾追加0
    split_with_index(left_part, current_idx + "0", res_map)
    # 递归处理右子树，父索引末尾追加1
    split_with_index(right_part, current_idx + "1", res_map)

if __name__ == "__main__":
    class_names = [1,2,3,4,5,6,7,8,9,10]
    index_map = {}
    split_with_index(class_names, "0", index_map)
    # 按索引长度从短到长输出，和树形层级顺序对应
    for split_node, idx in sorted(index_map.items(), key=lambda x: len(x[1])):
        # 转换为和原格式一致的列表形式输出
        print(f"{[list(part) for part in split_node]} = {idx}")

运行结果 #

[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]] = 0
[[1, 2], [3, 4, 5]] = 00
[[6, 7], [8, 9, 10]] = 01
[[1], [2]] = 000
[[3], [4, 5]] = 001
[[6], [7]] = 010
[[8], [9, 10]] = 011
[[4], [5]] = 0011
[[9], [10]] = 0111

输出完全匹配给定索引规则：根节点索引为0，任意节点的左子节点索引为父索引末尾追加0，右子节点为父索引末尾追加1，和示例给出的映射关系完全一致。

内容的提问来源于stack exchange，提问作者Ash