Chương trình tìm số nút lá và nút không phải lá của cây nhị phân bằng Python

Cho cây nhị phân, trả về cặp số: (số nút lá, số nút không phải lá).

Ví dụ: cây có 3 nút lá và 2 nút không phải lá → (3, 2).

Quy trình giải quyết (Đệ quy)

1. Nếu nút None, trả về (0, 0).
2. Nếu nút là lá (không có con trái và phải), trả về (1, 0).
3. Đệ quy tính cho con trái và con phải.
4. Trả về (left[0] + right[0], 1 + left[1] + right[1]).

Ví dụ mã nguồn

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))  # Output: (3, 2)

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