Chương trình đếm có bao nhiêu cách chúng ta có thể chia cây thành hai cây trong Python

Giả sử chúng ta có một cây nhị phân chứa các giá trị 0, 1 và 2. Gốc có ít nhất một nút 0 và một nút 1. Bây giờ, giả sử có một phép toán trong đó chúng ta xóa một cạnh trong cây và cây trở thành hai cây khác nhau. Chúng ta phải tìm số cách chúng ta có thể xóa một cạnh sao cho không cây nào trong hai cây chứa cả nút 0 và nút 1.

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

thì đầu ra sẽ là 1 vì chúng ta chỉ có thể xóa cạnh 0 đến 2.

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

• số lượng:=[0, 0, 0]
• Định nghĩa một hàm dfs (). Điều này sẽ lấy nút
• nếu nút không rỗng, thì
  • pre:=count
  • dfs (bên trái của nút)
  • dfs (bên phải của nút)
  • count [giá trị của nút]:=count [giá trị của nút] + 1
  • node.count:=danh sách (count [i] - pre [i]) đối với tôi là 0 và 1
• Xác định một hàm dfs2 (). Điều này sẽ lấy nút, mệnh
• nếu nút không rỗng, thì
  • nếu par không rỗng, thì
    • (a0, a1):=số lượng nút
    • (b0, b1):=(count [0] - a0, count [1] - a1)
    • nếu (a0 giống 0 hoặc a1 giống 0) và (b0 giống 0 hoặc b1 giống 0), thì
      • ans:=ans + 1
  • dfs2 (bên trái của nút, nút)
  • dfs2 (bên phải của nút, nút)
• Từ phương pháp chính, hãy thực hiện như sau -
• dfs (gốc)
• ans:=0
• dfs2 (gốc)
• 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, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      count = [0, 0, 0]
   def dfs(node):
      if node:
         pre = count[:]
         dfs(node.left)
         dfs(node.right)
         count[node.val] += 1
         node.count = [count[i] - pre[i] for i in range(2)]
   dfs(root)
   def dfs2(node, par=None):
      if node:
         if par is not None:
            a0, a1 = node.count
            b0, b1 = count[0] - a0, count[1] - a1
            if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0):
               self.ans += 1
         dfs2(node.left, node)
         dfs2(node.right, node)
   self.ans = 0
   dfs2(root)
   return self.ans
ob = Solution()
root = TreeNode(0)
root.left = TreeNode(0)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
print(ob.solve(root))

Đầu vào

root = TreeNode(0)
root.left = TreeNode(0)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)

Đầu ra

1