โปรแกรมหาโหนดลึกที่สุดด้านซ้ายมือในต้นไม้ไบนารีด้วย Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องการหาค่าของโหนดที่ลึกที่สุด (deepest node) หากมีโหนดลึกที่สุดมากกว่าหนึ่งโหนด ให้คืนค่าโหนดที่อยู่ซ้ายมือสุด (leftmost)

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ดังรูป ผลลัพธ์จะเป็น 4 เนื่องจาก 4 และ 7 ลึกเท่ากันแต่ 4 อยู่ซ้ายกว่า

ขั้นตอนการแก้ปัญหา (BFS Level Order)

1. queue = [root]
2. left_max = root.val
3. วนลูป while len(queue) > 0:
   • level_size = len(queue)
   • วนลูป i จาก 0 ถึง level_size - 1:
     • temp = queue.pop(0)
     • หาก i == 0 ให้ left_max = temp.val (โหนดแรกของระดับ = ซ้ายมือสุด)
     • เพิ่ม temp.left และ temp.right เข้า queue (ถ้ามี)
4. คืนค่า left_max (จะเป็นโหนดซ้ายมือสุดของระดับล่างสุด)

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

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

class Solution:
    def solve(self, root):
        queue = [root]
        left_max = root.val
        
        while len(queue) > 0:
            level_size = len(queue)
            for i in range(level_size):
                temp = queue.pop(0)
                if i == 0:
                    left_max = temp.val
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
        
        return left_max

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)
print(ob.solve(root))  # Output: 4

อินพุต

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)

เอาต์พุต

4