Chương trình tìm tổng của đường dẫn tổng dài nhất từ ​​gốc đến lá của cây nhị phân trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng của đường đi dài nhất từ ​​nút gốc đến nút lá. Nếu có hai đường dẫn dài giống nhau, hãy trả về đường dẫn có tổng lớn hơn.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 20.

Để 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 rec (). Điều này sẽ mất nhiều thời gian

• nếu curr là null thì

  • trở lại (0, 0)

• lớn hơn:=tối đa của rec (bên trái của curr), rec (bên phải của curr)

• trả về một cặp (lớn hơn [0] + 1, lớn hơn [1] + giá trị của curr)

• Từ phương thức chính, hãy làm như sau -

• ret:=rec (root)

• trả về chỉ mục thứ 1 của ret

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, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

Đầu vào

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

Đầu ra

20