Chương trình tìm đường dẫn giá trị chẵn dài nhất 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 đường đi dài nhất bao gồm các giá trị chẵn giữa hai nút bất kỳ trong cây.

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

thì đầu ra sẽ là 5 vì đường dẫn dài nhất là [10, 2, 4, 8, 6].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0

• Định nghĩa một hàm find (). Điều này sẽ lấy nút

• nếu nút là null, thì

  • return (-1, -1)

• leftCnt:=giá trị tối đa được trả về của tìm kiếm (bên trái của nút) + 1

• rightCnt:=giá trị trả về tối đa của tìm kiếm (bên phải của nút) + 1

• nếu giá trị của nút là chẵn thì

  • ans:=tối đa ans và (leftCnt + rightCnt + 1)

  • return (leftCnt, rightCnt)

• nếu không,

  • ans:=tối đa ans, leftCnt và rightCnt

  • return (-1, -1)

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

• tìm (root)

• 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, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
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

5