পাইথনে পাতা থেকে শুরু হওয়া ক্ষুদ্রতম স্ট্রিং

ধরুন আমাদের একটি বাইনারি গাছের মূল রয়েছে, প্রতিটি নোডে 0 থেকে 25 পর্যন্ত একটি মান রয়েছে, যা 'a' থেকে 'z' অক্ষরগুলিকে প্রতিনিধিত্ব করছে:0-এর মান 'a'-এর প্রতিনিধিত্ব করে, 1-এর মান 'b'-এর প্রতিনিধিত্ব করে ', এবং তাই। আমাদের অভিধানের দিক থেকে সবচেয়ে ছোট স্ট্রিংটি অনুসন্ধান করতে হবে যা এই গাছের একটি পাতা থেকে শুরু হয় এবং মূলে শেষ হয়। তাই গাছটি যদি −

তারপর আউটপুট হবে "adz" কারণ ক্রমটি [0,3,25]

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

• নিম্নরূপ একটি dfs ট্রাভার্সাল পদ্ধতি সংজ্ঞায়িত করুন

• যদি নোড নাল না হয়, তাহলে

  • A

    এ একটি অক্ষর হিসাবে নোড মান সন্নিবেশ করান

  • যদি নোডের বাম এবং ডান সন্তান না থাকে, তাহলে

    • ans :=ন্যূনতম উত্তর এবং A উপাদানগুলি বিপরীত আকারে স্ট্রিং হিসাবে

    • A

      থেকে শেষ উপাদান মুছুন

    • ফেরত

  • dfs (নোডের বামে, A)

    সম্পাদন করুন

  • dfs (নোডের ডানদিকে, A)

    সম্পাদন করুন

  • A

    থেকে শেষ উপাদান মুছুন

  • ফেরত

• প্রকৃত পদ্ধতি হবে −

  এর মত

• উত্তর :=“~”

• dfs(root, A হিসাবে একটি খালি অ্যারে)

  কল করুন

• উত্তর ফেরত দিন

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

উদাহরণ

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 smallestFromLeaf(self, root):
      self.ans = "~"
      self.dfs(root,[])
      return self.ans
   def dfs(self, node, A):
      if node:
         A.append(chr(node.data + ord('a')))
         if not node.left and not node.right:
            self.ans = min(self.ans, ''.join(reversed(A)))
            A.pop()
            return
      self.dfs(node.left,A)
      self.dfs(node.right,A)
      A.pop()
      return
root = make_tree([25,1,3,1,3,0,2])
ob = Solution()
print(ob.smallestFromLeaf(root))

ইনপুট

[25,1,3,1,3,0,2]

আউটপুট

adz