পাইথনে বাইনারি ট্রি জিগজ্যাগ লেভেল অর্ডার ট্রাভার্সাল

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের জিগজ্যাগ লেভেল অর্ডার ট্রাভার্সাল খুঁজে বের করতে হবে। তাই প্রথম সারির জন্য, বাম থেকে ডানে স্ক্যান করুন, তারপর দ্বিতীয় সারি থেকে ডান থেকে বামে, তারপর আবার বাম থেকে ডানে এবং আরও অনেক কিছু। তাই গাছটি যদি −

ট্রাভার্সাল সিকোয়েন্স হবে [[3],[20,9],[15,7]]

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

• গাছটি খালি থাকলে, খালি তালিকা ফেরত দিন

• সারি :=একটি সারি তৈরি করুন এবং সারিতে রুট সন্নিবেশ করুন, দুটি খালি তালিকা res এবং res2 তৈরি করুন এবং ফ্ল্যাগটিকে True হিসাবে সেট করুন

• যখন সারি খালি থাকে না

  • সারিতে উপস্থিত নোডগুলির একটি তালিকা তৈরি করুন, তারপরে res এ সন্নিবেশ করুন

  • নোডের মানগুলির একটি তালিকা তৈরি করুন যা সারিতে উপস্থিত রয়েছে, তারপরে res2 এ প্রবেশ করান

  • যদি পতাকা সেট করা হয়, তাহলে

    • i :=শেষ সাব-লিস্টের দৈর্ঘ্য রেজাল্ট – 1

    • যখন i>=0

      • যদি res-এর শেষ সাব-লিস্টের ith উপাদানটির ডান সাবট্রি থাকে, তাহলে

        • সারিতে ডান সাবট্রি ঢোকান

      • যদি res-এ শেষ সাব-লিস্টের ith উপাদানটি সাবট্রি ছেড়ে যায়, তাহলে

        • সারিতে বাম সাবট্রি ঢোকান

      • i 1 দ্বারা হ্রাস করুন

  • অন্যথায়

    • i :=শেষ সাব-লিস্টের দৈর্ঘ্য রেজাল্ট – 1

    • যখন i>=0

      • যদি res-এর শেষ সাব-লিস্টের ith উপাদানটির ডান সাবট্রি থাকে, তাহলে

        • সারিতে ডান সাবট্রি ঢোকান

      • যদি res-এ শেষ সাব-লিস্টের ith উপাদানটি সাবট্রি ছেড়ে যায়, তাহলে

        • সারিতে বাম সাবট্রি ঢোকান

      • i 1 দ্বারা হ্রাস করুন

• রিটার্ন res2

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def zigzagLevelOrder(self, root):
      if not root:
         return []
      queue = [root]
      res = []
      res2=[]
      flag = True
      while len(queue)!=0:
         res.append([i for i in queue])
         res2.append([i.data for i in queue if i.data != 0])
         queue = []
         if flag:
            i=len(res[-1])-1
         while i>=0:
            if res[-1][i].right:
               queue.append(res[-1][i].right)
            if res[-1][i].left:
               queue.append(res[-1][i].left)
            i-=1
         else:
            i=len(res[-1])-1
            while i>=0:
               if res[-1][i].left:
                  queue.append(res[-1][i].left)
               if res[-1][i].right:
                  queue.append(res[-1][i].right)
               i-=1
            flag = not flag
         return res2
ob = Solution()
tree = make_tree([3,9,20,None,None,15,7])
print(ob.zigzagLevelOrder(tree))

ইনপুট

[3,9,20,null,null,15,7]

আউটপুট

[[3], [20, 9], [15, 7]]