常规树的定义及基于指定输入格式用Python实现非二叉树高度计算的技术问询

Hey folks! Let's walk through how to compute the height of a non-binary tree in Python, following the specific input format you've laid out.

Problem Breakdown #

Input Format #

• First line: An integer n representing the number of vertices in the tree.
• Second line: n integers ranging from -1 to n-1. Each integer corresponds to the parent index of the vertex at that position:
  • If the value for vertex i (0 ≤ i ≤ n-1) is -1, then vertex i is the root of the tree.
  • The input is guaranteed to form a valid tree with exactly one root.

Output Format #

We need to output the height of the tree. For context, the height here is defined as the number of vertices along the longest path from the root to any leaf node.

Example Walkthrough #

Let's take the sample input to see how it maps to a tree:

Input:

5
4 -1 4 1 1

Output: 3

If we align the vertex indices (0-4) with their parent values, we get this mapping:

This translates to the tree structure:

1
   / \
  3   4
     / \
    0   2

Here, vertex 1 is the root. Its children are 3 and 4, and 4 has children 0 and 2. The longest path from root to leaf is 1 → 4 → 2, which has 3 vertices—hence the height is 3.

Python Implementation #

We have two solid approaches to solve this: recursive traversal and iterative BFS (breadth-first search). Let's cover both.

Approach 1: Recursive Calculation #

This method is straightforward—we build a map of parent-to-children, then recursively compute the height of each node (a node's height is 1 plus the maximum height of its children).

def calculate_tree_height(parent_list):
    # Build a dictionary to track each node's children
    children = {}
    root = -1
    for idx, parent in enumerate(parent_list):
        if parent == -1:
            root = idx
        else:
            if parent not in children:
                children[parent] = []
            children[parent].append(idx)
    
    # Recursive helper to get height of a given node
    def get_node_height(node):
        # Leaf node has no children, height is 1
        if node not in children:
            return 1
        # Find the tallest child, add 1 for the current node
        max_child_height = 0
        for child in children[node]:
            child_height = get_node_height(child)
            if child_height > max_child_height:
                max_child_height = child_height
        return max_child_height + 1
    
    return get_node_height(root)

# Handle input and output
n = int(input())
parent_values = list(map(int, input().split()))
print(calculate_tree_height(parent_values))

Approach 2: Iterative BFS (Level Order Traversal) #

If your tree is extremely deep, recursion might hit Python's default recursion limit. BFS avoids this by traversing the tree level by level, counting each level as a step in the height.

from collections import deque

def calculate_tree_height(parent_list):
    children = {}
    root = -1
    for idx, parent in enumerate(parent_list):
        if parent == -1:
            root = idx
        else:
            if parent not in children:
                children[parent] = []
            children[parent].append(idx)
    
    # Edge case: empty tree (though problem says there's one root)
    if root == -1:
        return 0
    
    height = 0
    # Use a queue to track nodes at the current level
    node_queue = deque([root])
    
    while node_queue:
        # Number of nodes in the current level
        level_size = len(node_queue)
        height += 1
        # Process all nodes in the current level
        for _ in range(level_size):
            current_node = node_queue.popleft()
            # Add all children to the queue for next level
            if current_node in children:
                node_queue.extend(children[current_node])
    
    return height

# Handle input and output
n = int(input())
parent_values = list(map(int, input().split()))
print(calculate_tree_height(parent_values))

Quick Notes on Both Approaches #

• Both methods first build a children dictionary to efficiently look up each node's descendants.
• Recursion is cleaner for small to moderately sized trees, while BFS is more robust for very deep trees.
• Both will correctly return the height of 3 for the sample input.

备注：内容来源于stack exchange，提问作者tươnghoàng