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

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

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

จากนั้นผลลัพธ์จะเป็น 4 เนื่องจาก 4 และ 7 นั้นลึกที่สุด แต่เหลือ 4 มากที่สุด

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

• คิว :=คิวที่มีหนึ่งโหนดรูท

• left_max :=ค่าของรูท

• ในขณะที่ขนาดของคิว> 0 ทำ

  • level_size :=ขนาดของคิว

  • สำหรับฉันอยู่ในช่วง 0 ถึง level_size ทำ

    • temp :=องค์ประกอบแรกจากคิวแล้วลบออก

    • ถ้าฉันเหมือนกับ 0 แล้ว

      • left_max :=ค่าอุณหภูมิ

    • หากอุณหภูมิที่เหลือไม่เป็นศูนย์

      • แทรกด้านซ้ายของ temp ที่ส่วนท้ายของคิว

    • ถ้า right of temp ไม่เป็นโมฆะ

      • แทรกด้านขวาของ temp ที่ท้ายคิว

  • กลับ left_max

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

ตัวอย่าง

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))

อินพุต

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