পাইথনে লিফ থেকে ছোট স্ট্রিং বের করা

মনে করুন আমাদের একটি বাইনারি ট্রির রুট দেওয়া আছে, প্রতিটি নোড ০ থেকে ২৫ এর ভ্যালু ধারণ করে যা 'a' থেকে 'z' রিপ্রেজেন্ট করে: ০ মানে 'a', ১ মানে 'b', ইত্যাদি। আমাদের লেক্সিকোগ্রাফিক্যালি স্মলেস্ট স্ট্রিং বের করতে হবে যা একটি লিফ থেকে শুরু হয়ে রুটে শেষ হয়।

ট্রি যদি নিচের মতো হয়:

তবে আউটপুট হবে "adz", কারণ সিকোয়েন্স [0,3,25]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (DFS + ব্যাকট্র্যাকিং):

• DFS ট্রভার্সাল মেথড ডিফাইন করুন:

  • যদি node null না হয়:

    • A.append(chr(node.data + ord('a')))

    • যদি লিফ নোড হয় (বাম ও ডান চাইল্ড নেই):

      • ans = min(ans, ''.join(reversed(A)))

      • A.pop(), রিটার্ন।

    • dfs(node.left, A)

    • dfs(node.right, A)

    • A.pop(), রিটার্ন।

• আসল মেথড:

  • ans := "~" (যেকোনো স্ট্রিংয়ের চেয়ে বড়)

  • dfs(root, []) কল করুন।

  • return ans

উদাহরণ

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