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

สมมติว่าเรามีต้นไม้ไบนารี เราต้องเช็คว่าใบทั้งหมดอยู่ในระดับเดียวกันหรือไม่

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() สิ่งนี้จะหยั่งราก d

• ถ้ารูทไม่เป็นโมฆะ

  • ถ้าทางซ้ายของรูทเป็นโมฆะ และทางขวาของรูทเป็นโมฆะ

    • แทรก d ที่ส่วนท้ายของความลึก

  • มิฉะนั้น

    • dfs(ทางซ้ายของรูท, d + 1)

    • dfs(ทางขวาของรูท, d + 1)

• จากวิธีหลัก ให้ทำดังนี้ −

• ความลึก :=รายการใหม่

• dfs(root, 0)

• คืนค่าจริงเมื่อความลึกมีค่าเพียงค่าเดียว

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

คลาส TreeNode:def __init__(self, value):self.val =value self.left =None self.right =Noneclass วิธีแก้ไข:def แก้ปัญหา (ตัวเอง, รูท):self.purpose =[] self.dfs (รูท) , 0) return len(set(self.depth)) ==1 def dfs(self, root, depth):ถ้า root:ถ้าไม่ใช่ root.left และไม่ใช่ root.right:self.depth.append(depth) อื่น:self.dfs (root.left, ความลึก + 1) self.dfs (root.right, ความลึก + 1)ob =โซลูชัน ()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) พิมพ์ (ob.solve (root))

อินพุต

ผลลัพธ์

จริง