โปรแกรมหาโหนดใบและโหนดไม่ใช่ใบของต้นไม้ทวิภาคใน Python

สมมติว่าเรามีต้นไม้ทวิภาค เราต้องหาลิสต์สองตัวเลข: ตัวแรกคือจำนวนโหนดใบ (leaves) ตัวที่สองคือจำนวนโหนดไม่ใช่ใบ (non-leaf nodes)

ตัวอย่าง: จากภาพ ผลลัพธ์คือ (3, 2) (3 ใบ, 2 โหนดไม่ใช่ใบ)

ขั้นตอนการแก้ปัญหา

1. ถ้า n เป็น None: คืนค่า (0, 0)
2. ถ้า n.left และ n.right เป็น None: คืนค่า (1, 0)
3. left = solve(n.left), right = solve(n.right)
4. คืนค่า (left[0] + right[0], 1 + left[1] + right[1])

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

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)

อินพุต / เอาต์พุต

Input: ต้นไม้ตามโค้ดตัวอย่าง

Output: (3, 2)