Python में n-ary ट्री का व्यास खोजने का प्रोग्राम

मान लीजिए, हमें एक n-ary ट्री दिया गया है और ट्री का व्यास निर्धारित करने के लिए कहा गया है। ट्री का व्यास ट्री के किन्हीं दो लीफ नोड्स के बीच मौजूद सबसे लंबा पथ है। हमें पूर्णांक मान वापस करना है जो ट्री के व्यास को दर्शाता है।

इसलिए, यदि इनपुट निम्न ट्री है:

तो आउटपुट 3 होगा।

इस n-ary ट्री का व्यास एज 27→14, 14→42, और 42→56 या 42→65 से मिलकर बनता है (आरेख में लाल रेखाओं द्वारा चिह्नित)। पथ की लंबाई 3 है।

हल करने के चरण

1. ans := 1
2. depth() फंक्शन परिभाषित करें जो root लेता है:
   • यदि root खाली नहीं है, तो 0 वापस करें
   • children := [0, 0] मान वाली नई सूची
   • temp_children := नई सूची
   • root के प्रत्येक child के लिए: temp_children के अंत में depth(child) डालें
   • यदि temp_children का आकार > 0, तो children := temp_children
   • ans := max(ans, sum(sorted(children)[-2:]) + 1)
   • max(children) + 1 वापस करें
3. depth(root) कॉल करें
4. (ans - 1) वापस करें

उदाहरण (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

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))

इनपुट

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

आउटपुट

3