สมมติว่าเรามีรูทของไบนารีทรี แต่ละโหนดมีค่าตั้งแต่ 0 ถึง 25 ซึ่งแทนตัวอักษร 'a' ถึง 'z':ค่า 0 แทน 'a' ค่า 1 แทน 'b ' และอื่นๆ เราต้องค้นหาสตริงที่เล็กที่สุดเกี่ยวกับศัพท์เฉพาะที่เริ่มต้นที่ใบไม้ของต้นไม้ต้นนี้และสิ้นสุดที่ราก ดังนั้นถ้าต้นไม้เป็นเหมือน −
จากนั้นผลลัพธ์จะเป็น “adz” ตามลำดับคือ [0,3,25]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการข้ามผ่าน dfs ดังนี้
-
ถ้าโหนดไม่เป็นโมฆะ
-
แทรกค่าโหนดเป็นอักขระลงใน A
-
ถ้าโหนดไม่มีลูกซ้ายและขวา
-
ans :=ขั้นต่ำขององค์ประกอบ ans และ A เป็นสตริงในรูปแบบย้อนกลับ
-
ลบองค์ประกอบสุดท้ายออกจาก A
-
กลับ
-
-
ดำเนินการ dfs (ด้านซ้ายของโหนด A)
-
ดำเนินการ dfs (ด้านขวาของโหนด A)
-
ลบองค์ประกอบสุดท้ายจาก A
-
กลับ
-
-
วิธีการจริงจะเป็นเช่น -
-
ตอบ :=“~”
-
เรียก dfs(root, อาร์เรย์ว่างเป็น 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
