โปรแกรมตรวจสอบว่าใบไม้ทุกใบอยู่ระดับเดียวกันหรือไม่ใน Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องตรวจสอบว่าใบไม้ (leaf nodes) ทุกใบอยู่ที่ระดับเดียวกันหรือไม่

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ดังรูป ผลลัพธ์จะเป็น True

ขั้นตอนการแก้ปัญหา (DFS เก็บความลึกของใบไม้)

1. สร้างฟังก์ชัน dfs(root, depth):
   • หาก root ไม่ใช่ null:
     • หากเป็นใบไม้ (not root.left and not root.right) ให้เพิ่ม depth เข้า list depth
     • มิฉะนั้น เรียก dfs(root.left, depth + 1) และ dfs(root.right, depth + 1)
2. จากเมธอดหลัก:
   • depth = []
   • เรียก dfs(root, 0)
   • คืนค่า True หาก len(set(depth)) == 1 (ทุกค่าใน depth เท่ากัน)

ตัวอย่างโค้ด Python

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

อินพุต

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)

เอาต์พุต

True