पायथन में समान स्तरों पर पत्तियों के डेटा के योग का गुणन प्राप्त करें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें निम्नलिखित ऑपरेशन करने हैं -

• प्रत्येक स्तर के लिए, यदि इस स्तर पर पत्तियाँ हैं तो सभी पत्तों का योग ज्ञात कीजिए। अन्यथा इसे अनदेखा करें।

• सभी राशियों का गुणन ज्ञात करें और उसे वापस करें।

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

तो आउटपुट 270 होगा। पहले दो स्तरों में कोई पत्ता नहीं है। तीसरे स्तर में एकल पत्ती 9 है। अंतिम स्तर में चार पत्ते 2, 12, 5 और 11 हैं। तो परिणाम 9 * (2 + 12 + 5 + 11) =270

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

• अगर रूट शून्य है, तो

  • वापसी 0

• रेस :=1

• कतार:=एक कतार

• कतार के अंत में जड़ डालें

• असीम रूप से करें -

  • no_of_nodes:=कतार का आकार

  • अगर no_of_nodes 0 के समान है, तो

    • लूप से बाहर आएं

  • sum_level :=0

  • पाया_पत्ती :=असत्य

  • जबकि no_of_nodes> 0, करें

    • curr_node :=क्यू का पहला तत्व

    • अगर curr_node पत्ती है, तो

      • पाया_पत्ती :=सच

      • sum_level :=sum_level + curr_node.data

    • क्यू से पहला तत्व हटाएं

    • अगर curr_node.left शून्य नहीं है, तो

      • क्यू के अंत में curr_node.left डालें

    • अगर curr_node.right शून्य नहीं है, तो

      • क्यू के अंत में curr_node.right डालें

    • no_of_nodes:=no_of_nodes - 1

  • अगर फाउंड_लीफ सच है, तो

    • रेस :=रेस * योग_लेवल

• रिटर्न रेस

उदाहरण

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

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def isLeaf(root) :
   return (not root.left and not root.right)
def find_res(root) :
   if (not root) :
      return 0
   res = 1
   que = []
   que.append(root)
   while (True):
      no_of_nodes = len(que)
   if (no_of_nodes == 0) :
      break
   sum_level = 0
   found_leaf = False
   while (no_of_nodes > 0) :
      curr_node = que[0]
      if (isLeaf(curr_node)) :
         found_leaf = True
         sum_level += curr_node.data
         que.pop(0)
         if (curr_node.left != None) :
            que.append(curr_node.left)
         if (curr_node.right != None) :
            que.append(curr_node.right)
         no_of_nodes -=1
      if (found_leaf) :
         res *= sum_level
   return res
root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)
print(find_res(root))

इनपुट

root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)

आउटपुट

270