Python实现树结构计算树高时子节点无法追加问题排查

原代码核心问题 #

原代码无法正常追加子节点、计算结果错误，由以下几个直接问题导致：

• 缩进语法错误：node类的__init__、set_parent、set_data方法，以及tree类的get_nodes方法均未缩进至类定义块内部，不属于类的实例方法，实例化节点时不会执行自定义初始化逻辑。
• 类属性与实例属性混淆：将children=[]定义为node类的类属性，所有节点实例会共享同一个子节点列表，无法为单个节点维护独立的子节点集合；tree类的nodes、root也存在同样的类属性误用问题。
• 输入处理错误：一是input().split()读取的内容为字符串类型，未转换为整数就做数值比较，所有匹配逻辑永远不成立；二是根节点判断条件写反，原逻辑判断索引n==-1，实际规则是节点存储的父节点值为-1时才是根节点，导致根节点从未被正确识别。
• 父子匹配逻辑写反：原逻辑判断p.data == c.parent，但实际节点创建时错误将当前节点索引传入parent参数，data字段存储的是父节点索引，匹配条件完全颠倒。
• 高度递归逻辑错误：递归计算子树高度时，仅创建了新的树实例、赋值了根节点的基础属性，没有将对应子节点挂载上去，递归无法遍历到树的深层节点。

修正后可运行代码 #

class Node:
    def __init__(self, parent, data):
        self.parent = parent
        self.data = data
        # 每个节点实例独立维护子节点列表
        self.children = []

    def set_parent(self, parent):
        self.parent = parent

    def set_data(self, data):
        self.data = data

def create_node(parent, data):
    return Node(parent, data)

class Tree:
    def __init__(self):
        # 每个树实例独立维护节点列表和根节点
        self.nodes = []
        self.root = None

    def set_root(self, data, parent=None):
        self.root = Node(parent, data)
        return self.root

    def get_root(self):
        return self.root

    def get_nodes(self):
        return self.nodes

def cal_height(root):
    # 直接基于节点递归，无需重复创建树实例
    if not root.children:
        return 1
    max_child_height = 0
    for child in root.children:
        current_h = cal_height(child)
        if current_h > max_child_height:
            max_child_height = current_h
    return 1 + max_child_height

# 读取输入，统一转为整数
node_count = int(input())
parent_index_list = list(map(int, input().split()))
tree = Tree()

# 初始化所有节点
for node_idx in range(node_count):
    parent_val = parent_index_list[node_idx]
    if parent_val == -1:
        # 父值为-1的节点设为根
        root = tree.set_root(data=node_idx, parent=None)
        tree.nodes.append(root)
    else:
        new_node = create_node(parent=parent_val, data=node_idx)
        tree.nodes.append(new_node)

# 关联父子关系
for parent_node in tree.nodes:
    for child_node in tree.nodes:
        if child_node.parent == parent_node.data:
            parent_node.children.append(child_node)

# 输出树高度
print(cal_height(tree.get_root()))

测试验证 #

测试输入：
5
4 -1 4 1 1
预期输出：3
对应树结构：根为索引1的节点，子节点是索引3、4；索引4的子节点是索引0、2，最长根到叶路径长度为3，计算结果符合预期。

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