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

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

फिर आउटपुट "adz" होगा क्योंकि अनुक्रम [0,3,25]

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

• एक डीएफएस ट्रैवर्सल विधि को निम्नानुसार परिभाषित करें

• यदि नोड शून्य नहीं है, तो

  • ए में एक वर्ण के रूप में नोड मान डालें

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

    • उत्तर:=न्यूनतम उत्तर और ए तत्व स्ट्रिंग के रूप में उल्टे रूप में

    • ए से अंतिम तत्व हटाएं

    • वापसी

  • प्रदर्शन dfs (नोड के बाएँ, A)

  • प्रदर्शन dfs (नोड का अधिकार, 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