Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng lớn nhất của bất kỳ đường dẫn nào đi từ nút gốc đến nút lá.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 29 như từ gốc, nếu chúng ta đi theo đường dẫn 5- <9- <7- <8 thì sẽ là 29 sau khi cộng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
Định nghĩa một hàm walk (). Điều này sẽ lấy nút, s
-
nếu nút là null, thì
-
max_sum:=tối đa max_sum và s
-
trở lại
-
-
s:=s + dữ liệu của nút
-
đi bộ (bên trái của nút, các)
-
đi bộ (bên phải của nút, các)
-
Từ phương thức chính, hãy làm như sau−
-
max_sum:=0
-
đi bộ (root, 0)
-
trả về max_sum
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn−
Ví dụ
from collections import defaultdict class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def walk(self, node, s): if not node: self.max_sum = max(self.max_sum, s) return s += node.data self.walk(node.left, s) self.walk(node.right, s) def solve(self, root): self.max_sum = 0 self.walk(root, 0) return self.max_sum ob = Solution() root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))
Đầu vào
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
Đầu ra
29