Chương trình tìm số con duy nhất trong 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 số nút là con một. Như chúng ta biết, nút x được gọi là nút con duy nhất khi nút cha của nó có đúng một nút con là x.

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

thì đầu ra sẽ là 2 vì 8 và 6 là con duy nhất.

Để 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
• d:=một hàng đợi kết thúc kép
• chèn thư mục gốc vào cuối d
• số lượng:=0
• trong khi d không trống, hãy thực hiện
  • current:=phần tử bên trái của d và xóa phần tử bên trái
  • nếu left of current không phải là null, thì
    • chèn bên trái dòng điện vào d
    • nếu quyền hiện tại là null, thì
      • count:=count + 1
    • nếu quyền hiện tại không rỗng, thì
      • chèn bên phải dòng điện vào d
      • nếu bên trái của hiện tại là null, thì
        • count:=count + 1
• số lượng trả lại

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

Mã mẫu

from collections import deque

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
      d = deque()
      d.append(root)
      count = 0
      while d:
         current = d.popleft()
         if current.left:
            d.append(current.left)
            if not current.right:
               count += 1
            if current.right:
               d.append(current.right)
               if not current.left:
                  count += 1
         return count

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
print(ob.solve(root))

Đầu vào

root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)

Đầu ra

2