求助：使用叶节点与内部节点列表构建Python二叉树

Hey，我看了你写的二叉树构建代码，发现递归逻辑存在明显问题，导致没法正常生成符合要求的树。咱们一步步来拆解问题，再给出可行的修复方案。

原代码的核心问题 #

你的buildtree函数递归逻辑完全偏离了需求：

• 错误地把叶节点添加到内部节点列表里，这相当于把本该是叶子的节点当成了非叶子节点处理，完全违背了两个输入列表的分工
• 递归调用时，左右子树共享同一个leafs[1:]，会导致叶节点被重复使用，根本没法正确分配到树的各个叶子位置
• 内部节点没有按顺序被消耗，反而不断累加，最终会导致大量重复节点出现

正确的构建思路 #

你的输入刚好满足满二叉树的特性：叶节点数 = 内部节点数 + 1（4个叶子，3个内部节点）。针对这种结构，递归构建的核心逻辑应该是这样的：

1. 如果没有可用的内部节点了，说明当前要创建的是叶子节点，直接用叶节点列表的第一个元素生成Node
2. 否则，取第一个内部节点作为当前的根节点
3. 把剩余的内部节点拆分给左右子树：左子树分配(总内部节点数-1)//2个，右子树拿剩下的
4. 把叶节点列表平均拆成两部分，分别交给左右子树使用
5. 递归构建左右子树，最后把它们挂载到根节点上

修复后的完整代码 #

class Node:
    def __init__(self, data="", pos=None, neg=None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg

def buildtree(childs_in_tree, leafs):
    # 没有内部节点时，直接创建叶子节点
    if not childs_in_tree:
        return Node(leafs[0])
    
    # 取当前第一个内部节点作为根节点的数据
    root_data = childs_in_tree[0]
    # 计算左子树需要的内部节点数量
    left_internal_count = (len(childs_in_tree) - 1) // 2
    # 拆分内部节点，分配给左右子树
    left_internal = childs_in_tree[1 : 1 + left_internal_count]
    right_internal = childs_in_tree[1 + left_internal_count :]
    # 拆分叶节点，左右子树各拿一半
    leaf_split = len(leafs) // 2
    left_leaves = leafs[:leaf_split]
    right_leaves = leafs[leaf_split:]
    
    # 递归构建左右子树
    left_child = buildtree(left_internal, left_leaves)
    right_child = buildtree(right_internal, right_leaves)
    
    # 创建根节点并返回
    return Node(root_data, left_child, right_child)

# 用你的输入测试
leafs = ['dead','healthy','cold','influenza']
childs_in_tree = ['cough','sneezing','fever']
root = buildtree(childs_in_tree, leafs)

验证结果 #

用你的输入测试时，生成的树结构完全符合预期：

• 根节点是cough，它的左子节点是sneezing，右子节点是fever
• sneezing的左右叶子分别是dead和healthy
• fever的左右叶子分别是cold和influenza
  返回的root变量就是这棵树的根节点，完全满足你的需求。

内容的提问来源于stack exchange，提问作者Oday Haj Yehia