पायथन में एक एन-आरी पेड़ का व्यास खोजने का कार्यक्रम

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

तो, अगर इनपुट पसंद है

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

उत्तर :=1
फ़ंक्शन गहराई () को परिभाषित करें। यह जड़ लेगा
- अगर रूट खाली नहीं है, तो
  - वापसी 0
- बच्चे :=0, 0 मानों वाली एक नई सूची
- temp_children :=एक नई सूची
- जड़ के बच्चों में प्रत्येक बच्चे के लिए, करें
  - temp_children के अंत में गहराई (बच्चा) डालें
- अगर आकार (temp_children)> 0, तो
  - बच्चे :=temp_child
- उत्तर:=अधिकतम उत्तर, योग (बच्चों की सूची को क्रमबद्ध करें [सूचकांक लंबाई (बच्चों) से - 2 से अंत तक]) + 1
- बच्चों की अधिकतम वापसी + 1
गहराई (रूट)
वापसी (उत्तर -1)

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Node:
   def __init__(self, value, child = None) -> None:
      self.val = value
      self.children = []
      if child != 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