Chương trình kiểm tra xem tất cả các lá có cùng cấp hay không bằng Python

Giả sử chúng ta có một cây nhị phân; chúng ta phải kiểm tra xem tất cả các lá có ở cùng mức độ hay không.

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

thì đầu ra sẽ là True

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

• Định nghĩa một hàm dfs (). Điều này sẽ bén rễ, d

• nếu root không null thì

  • nếu bên trái của thư mục gốc là null và bên phải của thư mục gốc là null, thì

    • chèn d ở cuối độ sâu

  • nếu không,

    • dfs (bên trái của thư mục gốc, d + 1)

    • dfs (bên phải của thư mục gốc, d + 1)

• Từ phương thức chính, thực hiện như sau -

• deep:=một danh sách mới

• dfs (gốc, 0)

• trả về true khi độ sâu chỉ có một giá trị

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, value):
      self.val = value
      self.left = None
      self.right = None

class Solution:
   def solve(self, root):
      self.depth = []
      self.dfs(root, 0)
      return len(set(self.depth)) == 1
   def dfs(self, root, depth):
      if root:
         if not root.left and not root.right:
            self.depth.append(depth)
         else:
            self.dfs(root.left, depth + 1)
            self.dfs(root.right, depth + 1)
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.left.left = TreeNode(2)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
print(ob.solve(root))

Đầu vào

root = TreeNode(5)
root.left = TreeNode(4)
root.left.left = TreeNode(2)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

Đầu ra

True