Chương trình tìm các nút lá và không phải lá 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 một danh sách gồm hai số trong đó số đầu tiên là số lá trong cây và số thứ hai là số nút không phải là lá.

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

thì đầu ra sẽ là (3, 2), vì có 3 nút lá và 2 nút không phải lá.

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

• nếu n rỗng, thì
  • return (0, 0)
• nếu bên trái của n là null và bên phải của n là rỗng, thì
  • return (1, 0)
• left:=giải quyết (bên trái của n)
• right:=giải quyết (bên phải của n)
• quay lại (trái [0] + phải [0], 1 + trái [1] + phải [1])

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, n):
      if not n:
         return 0, 0
      if not n.left and not n.right:
         return 1, 0
      left, right = self.solve(n.left), self.solve(n.right)
      return left[0] + right[0], 1 + left[1] + right[1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

Đầu vào

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

Đầu ra

(3, 2)