पायथन में लीफ से शुरू होने वाली सबसे छोटी स्ट्रिंग

मान लीजिए हमारे पास एक बाइनरी ट्री का रूट है, प्रत्येक नोड 0 से 25 तक का मान रखता है, जो 'a' से 'z' अक्षरों का प्रतिनिधित्व करते हैं: 0 का मान 'a' दर्शाता है, 1 का मान 'b' दर्शाता है, और इसी तरह। हमें लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग ढूंढनी है जो इस ट्री के लीफ से शुरू होती है और रूट पर समाप्त होती है। इसलिए यदि ट्री इस तरह है -

तब आउटपुट \"adz\" होगा क्योंकि क्रम [0,3,25] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• DFS ट्रैवर्सल मेथड को निम्नानुसार परिभाषित करें

• यदि node null नहीं है, तो

  • नोड मान को कैरेक्टर के रूप में A में इन्सर्ट करें

  • यदि नोड के बाएं और दाएं चाइल्ड नहीं हैं, तो

    • ans := ans और A एलिमेंट्स का रिवर्स्ड फॉर्म में स्ट्रिंग का न्यूनतम

    • A से अंतिम एलिमेंट डिलीट करें

    • लौटें

  • dfs(node का बायां, A) करें

  • dfs(node का दायां, A) करें

  • A से अंतिम एलिमेंट डिलीट करें

  • लौटें

• वास्तविक मेथड इस तरह होगा -

• ans := \"~\"

• dfs(root, A के रूप में खाली ऐरे) कॉल करें

• 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