โปรแกรมค้นหาโหนดที่ลึกที่สุดเป็นอันดับสองในไบนารีทรีใน python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาความลึกของใบที่ลึกที่สุดเป็นอันดับสอง หากมีใบที่ลึกที่สุดหลายใบ โหนดที่ลึกที่สุดเป็นอันดับสองจะเป็นโหนดสูงสุดอันดับถัดไป อย่างที่ทราบกันดีว่ารูทมีความลึกเป็น 0

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

จากนั้นผลลัพธ์จะเป็น 1 เนื่องจากโหนดที่ลึกที่สุดอันดับสองคือ 3

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

• ถ้ารูทเป็นโมฆะ
  • คืนค่า null
• โหนด :=รายการใหม่
• ใส่รูทที่ส่วนท้ายของโหนด
• นับ :=0, ก่อนหน้า :=0, ตอนนี้ :=0
• ในขณะที่โหนดไม่ว่าง ให้ทำ
  • ใหม่ :=รายการใหม่
  • flag :=จริง
  • สำหรับแต่ละโหนดในโหนด ให้ทำ
    • ถ้าแฟล็กเป็นจริงและ (ด้านซ้ายของโหนดเป็นโมฆะ) และ (ด้านขวาของโหนดเป็นโมฆะ) ดังนั้น
      • ก่อนหน้า :=ตอนนี้
      • ตอนนี้ :=นับ
      • ธง :=เท็จ
    • ถ้าทางซ้ายของโหนดไม่เป็นโมฆะ
      • แทรกด้านซ้ายของโหนดที่ส่วนท้ายของใหม่
    • ถ้าทางขวาของโหนดไม่เป็นโมฆะ
      • แทรกด้านขวาของโหนดที่ส่วนท้ายของใหม่
  • โหนด :=ใหม่
  • นับ :=นับ + 1
• ย้อนกลับก่อนหน้า

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

ตัวอย่าง

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

class Solution:
   def solve(self, root):
      if root is None:
         return None
      nodes = []
      nodes.append(root)
      count = 0
      prev = 0
      now = 0
      while nodes:
         new = []
         flag = True
         for node in nodes:
         if flag and (not node.left) and (not node.right):
            prev = now
            now = count
            flag = False
         if node.left:
            new.append(node.left)
         if node.right:
            new.append(node.right)
      nodes = new
      count += 1
   return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

อินพุต

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)

ผลลัพธ์

1