Chương trình kiểm tra tất cả lá có cùng cấp độ trong Python

Cho cây nhị phân, kiểm tra xem tất cả các nút lá (leaf) có nằm ở cùng một cấp độ (depth) hay không.

Ví dụ: cây như hình → kết quả True.

Giải thuật (DFS thu thập độ sâu lá)

1. Khởi tạo danh sách depth = [].
2. Định nghĩa dfs(root, d):
   • Nếu không None:
     • Nếu là lá (not root.left and not root.right): thêm vào .
     • Ngược lại: đệ quy dfs(root.left, d+1), dfs(root.right, d+1).
3. Gọi .
4. Trả về len(set(depth)) == 1 (tất cả độ sâu lá giống nhau).

Ví dụ minh họa

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))  # Output: True

Đầ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