Chương trình tìm độ dài của đường đi xen kẽ 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 xen kẽ giữa con trái và con phải và đi xuống.

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

thì đầu ra sẽ là 5 vì đường dẫn xen kẽ là [2, 4, 5, 7, 8].

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

• nếu gốc là null, thì
  • trả về 0
• Định nghĩa một hàm dfs (). Thao tác này sẽ lấy nút, đếm, gắn cờ
• nếu nút không rỗng, thì
  • nếu cờ giống với True, thì
    • a:=dfs (bên trái của nút, đếm + 1, Sai)
    • b:=dfs (bên phải của nút, 1, Đúng)
  • nếu không, khi cờ giống với False, thì
    • a:=dfs (bên phải nút, đếm + 1, Đúng)
    • b:=dfs (bên trái của nút, 1, Sai)
  • trả về tối đa a, b
• số lần trả lại
• Từ phương thức chính, hãy làm như sau:
• a:=dfs (left of root, 1, False)
• b:=dfs (bên phải gốc, 1, Đúng)
• trả về tối đa a, b

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

class Solution:
   def solve(self, root):
      if not root:
         return 0

      def dfs(node, count, flag):
         if node:
            if flag == True:
               a = dfs(node.left, count + 1, False)
               b = dfs(node.right, 1, True)
            elif flag == False:
               a = dfs(node.right, count + 1, True)
               b = dfs(node.left, 1, False)

            return max(a, b)
      return count

      a = dfs(root.left, 1, False)
      b = dfs(root.right, 1, True)

   return max(a, b)

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))

Đầu vào

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

Đầu ra

5