Python 中从叶子开始的最小字符串

pythonserver side programmingprogramming更新于 2025/11/14 14:36:17

假设我们有一个二叉树的根，每个节点包含一个从 0 到 25 的值，分别代表字母"a"到"z":0 值代表"a"，1 值代表"b"，依此类推。我们必须搜索从这棵树的叶子开始到根结束的字典顺序最小的字符串。因此，如果树像 −

则输出将是 “adz”因为序列是 [0,3,25]

为了解决这个问题，我们将遵循以下步骤 −

定义一个 dfs 遍历方法如下
如果节点不为空，则
- 将节点值作为字符插入 A
- 如果节点没有左子节点和右子节点，则
  - ans := ans 和 A 元素的最小值作为反转形式的字符串
  - 从 A 中删除最后一个元素
  - 返回
- 执行 dfs(节点左侧，A)
- 执行 dfs(节点右侧， A)
- 从 A 中删除最后一个元素
- 返回
实际方法如下 −
ans := “~”
call dfs(root, an empty array as 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))