পাইথনে একই স্তরে পাতার ডেটার যোগফলের গুণন খুঁজুন

ধরুন আমাদের একটি বাইনারি ট্রি আছে। আমাদের নিম্নলিখিত অপারেশনগুলি সম্পাদন করতে হবে -

প্রতিটি স্তরের জন্য, এই স্তরে পাতা থাকলে সমস্ত পাতার সমষ্টি খুঁজুন। অন্যথায় এটি উপেক্ষা করুন।
সমস্ত রাশির গুণ বের করুন এবং ফেরত দিন।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 270। প্রথম দুটি স্তরের কোনো পাতা নেই। তৃতীয় স্তরে 9টি একক পাতা রয়েছে৷ শেষ স্তরে চারটি পাতা রয়েছে 2, 12, 5 এবং 11৷ সুতরাং ফলাফল হল 9 * (2 + 12 + 5 + 11) =270

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যদি রুট শূন্য হয়, তাহলে
- রিটার্ন 0
res :=1
que :=একটি সারি
que এর শেষে রুট ঢোকান
অসীমভাবে করুন -
- no_of_nodes :=que এর আকার
- যদি no_of_nodes 0 এর মত হয়, তাহলে
  - লুপ থেকে বেরিয়ে আসুন
- sum_level :=0
- found_leaf :=মিথ্যা
- যখন no_of_nodes> 0, do
  - curr_node :=que এর প্রথম উপাদান
  - যদি curr_node পাতা হয়, তাহলে
    - found_leaf :=সত্য
    - sum_level :=sum_level + curr_node.data
  - que
    থেকে প্রথম উপাদান মুছুন
  - যদি curr_node.left শূন্য না হয়, তাহলে
    - que এর শেষে curr_node.left সন্নিবেশ করুন
  - যদি curr_node.right শূন্য না হয়, তাহলে
    - que এর শেষে curr_node.right সন্নিবেশ করুন
  - no_of_nodes :=no_of_nodes - 1
- যদি পাওয়া_পাতা সত্য হয়, তাহলে
  - res :=res * sum_level
রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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)