পাইথনে পর্যায়ক্রমে বাইনারি ট্রি লেভেল টাইপ করার প্রোগ্রাম

ধরুন আমাদের বাইনারি ট্রি আছে, আমাদের প্রতিটি স্তরের মান দেখাতে হবে বাম থেকে ডানে এবং ডান থেকে বামে যাওয়ার মাধ্যমে।

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

তাহলে আউটপুট হবে [5, -10, 4, -2, -7, 15]

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

• যদি রুট শূন্য হয়, তাহলে

  • একটি নতুন তালিকা ফেরত দিন

• s1 :=একটি তালিকা প্রাথমিকভাবে রুট সন্নিবেশ করান

• s2 :=একটি নতুন তালিকা

• res :=একটি নতুন তালিকা

• যখন s1 খালি নয় বা s2 খালি নয়, কর

  • যখন s1 খালি নয়, করুন

    • নোড :=s1 থেকে শেষ উপাদান মুছুন

    • যদি নোডের বাম অংশ শূন্য না হয়, তাহলে

      • s2

        এর শেষে নোডের বাম দিকে সন্নিবেশ করুন

    • যদি নোডের ডানদিকে শূন্য না হয়, তাহলে

      • s2

        -এর শেষে নোডের ডানদিকে সন্নিবেশ করুন

    • res এর শেষে নোডের মান সন্নিবেশ করান

  • যখন s2 খালি নয়, করুন

    • নোড :=s2 থেকে শেষ উপাদান মুছুন

    • যদি নোডের ডানদিকে শূন্য না হয়, তাহলে

      • s1

        এর শেষে নোডের ডানদিকে সন্নিবেশ করুন

    • যদি নোডের বাম অংশ খালি না হয়, তাহলে

      • s1

        এর শেষে নোডের বাম দিকে সন্নিবেশ করুন

    • res এর শেষে নোডের মান সন্নিবেশ করান

• রিটার্ন রিটার্ন

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if not root:
         return []
      s1 = [root]
      s2 = []
      res = []
      while s1 or s2:
         while s1:
            node = s1.pop()
            if node.left:
               s2.append(node.left)
            if node.right:
               s2.append(node.right)
            res.append(node.val)
         while s2:
            node = s2.pop()
            if node.right:
               s1.append(node.right)
            if node.left:
               s1.append(node.left)
            res.append(node.val)
      return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)
print(ob.solve(root))

ইনপুট

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)

আউটপুট

[5, -10, 4, -2, -7, 15]