資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告