Chương trình kiểm tra có thể tô màu cây nhị phân sao cho nút liền kề khác màu bằng Python

Cho cây nhị phân mỗi nút có giá trị là màu (tối đa 2 màu). Kiểm tra có thể hoán đổi màu các nút sao cho không có hai nút liền kề cùng màu hay không.

Ví dụ: cây đầu vào → True (có thể tô màu xen kẽ).

Giải thuật

• DFS duyệt cây, đếm số lượng từng màu thực tế (colors) và số lượng nút ở độ sâu chẵn/lẻ (prop với flag true/false).
• Nếu tập hợp các giá trị đếm của colors và prop trùng khớp → có thể tô màu xen kẽ → True.

Ví dụ minh họa

from collections import defaultdict
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        colors = defaultdict(int)
        prop = defaultdict(int)
        def dfs(node, flag=True):
            if not node:
                return
            colors[node.val] += 1
            prop[flag] += 1
            dfs(node.left, not flag)
            dfs(node.right, not flag)
        dfs(root)
        return set(colors.values()) == set(prop.values())

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
root.right.left.right = TreeNode(1)
print(ob.solve(root))

Đầu vào

root = TreeNode(2) ...

Đầu ra

True