Python中从叶子节点开始的最短字符串

假设我们有一棵二叉树的根节点，每个节点包含一个0到25之间的值，这些值代表字母'a'到'z'：值为0代表'a'，值为1代表'b'，以此类推。我们必须搜索从这棵树的叶子节点开始，到根节点结束的字典序最小的字符串。如果树是这样的：

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

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

• 定义一个深度优先搜索(DFS)遍历方法，如下所示：

• 如果节点不为空，则：

  • 将节点值作为字符插入到A中

  • 如果节点没有左子节点和右子节点，则：

    • ans := ans和A元素的反转字符串的最小值

    • 从A中删除最后一个元素

    • 返回

  • 执行dfs(节点的左子节点, A)

  • 执行dfs(节点的右子节点, A)

  • 从A中删除最后一个元素

  • 返回

• 实际方法如下：

• ans := “~”

• 调用dfs(根节点, 一个空数组作为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

Arnab Chakraborty

更新于：2020年5月2日

205 次浏览

启动你的职业生涯

完成课程获得认证

开始学习