โปรแกรมหา Diameter ของ N-ary Tree ใน Python

โจทย์

กำหนด N-ary Tree ให้หา Diameter (เส้นทางยาวที่สุดระหว่าง Leaf Node สองจุด) คืนค่าเป็นจำนวน Edge

ตัวอย่าง: Tree ที่มีโครงสร้าง 14 → (27, 32, 42) และ 42 → (56, 65) → Diameter = 3 (เส้นทาง 27-14-42-56 หรือ 27-14-42-65)

อัลกอริธึม (DFS + เก็บความลึกสูงสุด 2 ค่า)

1. DFS หาความลึกของแต่ละ Node
2. เก็บความลึกของลูกทุกตัว เรียงหา 2 ค่ามากที่สุด
3. อัปเดต ans = max(ans, sum(두ค่าสูงสุด) + 1)
4. คืน ans - 1 (เพราะนับเป็น Edge)

โค้ด Python

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

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

# สร้าง Tree ตัวอย่าง
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))  # Output: 3

Input / Output

Input:  Tree structure as above
Output: 3