Chương trình tìm đường kính của cây n-ary trong Python

Giả sử ta được cho một cây n-ary và yêu cầu xác định đường kính của cây. Đường kính của cây là đường đi dài nhất tồn tại giữa hai nút lá bất kỳ của cây. Ta phải tìm và trả về giá trị nguyên đại diện cho đường kính của cây.

Ví dụ với cây như hình, kết quả là 3. Đường kính bao gồm các cạnh 27→14, 14→42, và 42→56 hoặc 42→65. Độ dài đường đi là 3.

Giải thuật

1. ans := 1
2. Định nghĩa hàm depth(root):
   • Nếu root rỗng: trả về 0
   • children := [0, 0]
   • temp_children := []
   • Với mỗi child trong root.children:
     • Thêm depth(child) vào temp_children
   • Nếu len(temp_children) > 0: children := temp_children
   • ans := max(ans, sum(sorted(children)[-2:]) + 1)
   • Trả về max(children) + 1
3. Gọi depth(root)
4. Trả về ans - 1

Ví dụ (Python)

class Node:
    def __init__(self, value, child=None) -> None:
        self.val = value
        self.children = []
        if child is not None:
            for value in child:
                self.children.append(value)

ans = 1

def solve(root):
    def depth(root):
        global ans
        if not root:
            return 0
        children = [0, 0]
        temp_children = [depth(child) for child in root.children]
        if len(temp_children) > 0:
            children = temp_children
        ans = max(ans, sum(sorted(children)[-2:]) + 1)
        return max(children) + 1
    
    depth(root)
    return ans - 1

# Xây dựng cây
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1

print(solve(root))

Input

node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) root = node1

Output

3