โปรแกรมตรวจสอบ Binary Tree ว่า Node ทุกตัวมีค่าเท่ากันหรือไม่ (Python)

ปัญหา

กำหนด Binary Tree ตรวจสอบว่าทุก node มีค่าเท่ากันทุกตัวหรือไม่

วิธีแก้: Recursive DFS

เปรียบเทียบค่าแต่ละ node กับค่าราก (root value) ทั้งต้นไม้

อัลกอริทึม

1. ฟังก์ชัน solve(root, val=None)
2. ถ้า root เป็น None → True (empty tree valid)
3. ถ้า val ยังไม่ได้ตั้ง → val = root.val
4. คืนค่า: root.val == val AND solve(left) AND solve(right)

โค้ด Python

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, val=None):
        if not root:
            return True
        if val is None:
            val = root.val
        return (root.val == val and 
                self.solve(root.left, val) and 
                self.solve(root.right, val))

# ทดสอบ
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)

print(ob.solve(root))  # True

# ทดสอบ False case
root2 = TreeNode(5)
root2.left = TreeNode(5)
root2.right = TreeNode(3)  # ค่าต่าง
print(ob.solve(root2))  # False

ความซับซ้อน

• Time: O(n) - เยี่ยมทุก node 1 ครั้ง
• Space: O(h) - เรียกซ้ำสูงสุดความสูงต้นไม้ (h = height)

วิธีอื่น: Iterative BFS/DFS

def solve_iterative(self, root):
    if not root:
        return True
    target = root.val
    stack = [root]
    while stack:
        node = stack.pop()
        if node.val != target:
            return False
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return True

เวอร์ชัน iterative หลีกเลี่ยง recursion limit สำหรับต้นไม้ลึกมาก