Giả sử chúng ta có gốc của một cây nhị phân, mỗi nút chứa một giá trị từ 0 đến 25, chúng đại diện cho các chữ cái từ 'a' đến 'z':giá trị 0 đại diện cho 'a', giá trị 1 đại diện cho 'b ', và như thế. Chúng ta phải tìm kiếm chuỗi nhỏ nhất về mặt từ vựng bắt đầu từ lá của cây này và kết thúc ở gốc. Vì vậy, nếu cây như -
Sau đó, đầu ra sẽ là “adz” vì trình tự là [0,3,25]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định phương thức duyệt dfs như sau
-
nếu nút không phải là null, thì
-
chèn giá trị nút dưới dạng ký tự vào A
-
nếu nút không có nút con bên trái và bên phải, thì
-
ans:=tối thiểu các phần tử ans và A dưới dạng chuỗi ở dạng đảo ngược
-
xóa phần tử cuối cùng khỏi A
-
trở lại
-
-
thực hiện dfs (bên trái của nút, A)
-
thực hiện dfs (bên phải của nút, A)
-
Xóa phần tử cuối cùng khỏi A
-
trở lại
-
-
Phương pháp thực tế sẽ như thế nào -
-
ans:=“~”
-
gọi dfs (gốc, một mảng trống là A)
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[25,1,3,1,3,0,2]
Đầu ra
adz