สมมติว่ามีต้นไม้ไบนารี เราจะลบใบไม้ที่มีค่าเป็นเลขคู่ซ้ำๆ หลังจากลบหมด ถ้ามีเพียงรากที่เป็นเลขคู่ จะถูกลบด้วย
เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ ผลลัพธ์จะเป็นต้นไม้ที่เหลือหลังลบใบไม้เลขคู่
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน solve() รับ root
- ถ้า root เป็น null คืนค่า null
- left of root := solve(left of root)
- right of root := solve(right of root)
- ถ้า root เป็นใบไม้และข้อมูลของ root เป็นเลขคู่ คืนค่า null
- คืนค่า root
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=', ')
inorder(root.right)
class Solution:
def solve(self, root):
if not root:
return None
root.left = self.solve(root.left)
root.right = self.solve(root.right)
if not root.left and not root.right and root.data % 2 == 0:
return None
return root
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
ob.solve(root)
inorder(root)
อินพุต
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
เอาต์พุต
13, 16, 7, 14,
