Chương trình tìm độ dài của đường đi dài nhất với tổng chẵn bằng Python

Giả sử chúng ta có một cây nhị phân. chúng ta phải tìm độ dài của con đường dài nhất có tổng là một số chẵn.

Vì vậy, nếu đầu vào giống như hình ảnh, thì đầu ra sẽ là 5, vì đường dẫn giống như [5, 2, 4, 8, 5], sum =24 (chẵn).

Để 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 dfs (). Điều này sẽ lấy nút
• nếu nút là null, thì
  • trả về một cặp (0, -inf)
• (left_0, left_1):=dfs (left of node)
• (right_0, right_1):=dfs (bên phải của nút)
• nếu giá trị của nút là lẻ, thì
  • ans:=tối đa ans, (left_1 + right_0 + 1) và (left_0 + right_1 + 1)
  • trả về một cặp (tối đa là (left_1 + 1), (right_1 + 1) và 0), tối đa (left_0 + 1) và (right_0 + 1))
• nếu không,
  • ans:=tối đa ans, (left_0 + right_0 + 1) và (left_1 + right_1 + 1)
  • trả về một cặp (tối đa là (left_0 + 1), (right_0 + 1), 0), tối đa (left_1 + 1), (right_1 + 1))
• Từ phương thức chính, hãy làm như sau -
• ans:=0
• dfs (gốc)
• trả lại ans

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      def dfs(node):
         if not node:
            return 0, float("-inf")
         left_0, left_1 = dfs(node.left)
         right_0, right_1 = dfs(node.right)
         if node.val & 1:
            self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
            return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
         else:
            self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
            return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
   self.ans = 0
   dfs(root)
   return self.ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)
print(ob.solve(root))

Đầu vào

root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)

Đầu ra

5