数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学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
更新于：2020年5月2日
205 次浏览
广告