Chương trình tìm nút sâu thứ hai trong cây nhị phân trong python

Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm độ sâu của chiếc lá sâu thứ hai. Nếu có nhiều lá sâu nhất, nút lá sâu thứ hai sẽ là nút cao nhất tiếp theo. Như chúng ta biết gốc có độ sâu bằng 0.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 1, vì nút sâu thứ hai là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• nếu gốc là null, thì
  • trả về null
• các nút:=một danh sách mới
• chèn gốc vào cuối các nút
• đếm:=0, trước:=0, bây giờ:=0
• trong khi các nút không trống, hãy thực hiện
  • new:=một danh sách mới
  • cờ:=True
  • đối với mỗi nút trong các nút, hãy thực hiện
    • nếu cờ là true và (bên trái của nút là null) và (bên phải của nút là null), thì
      • trước đây:=bây giờ
      • bây giờ:=count
      • cờ:=Sai
    • nếu bên trái của nút không rỗng, thì
      • chèn bên trái của nút vào cuối mới
    • nếu bên phải của nút không rỗng, thì
      • chèn vào bên phải của nút ở cuối mới
  • các nút:=mới
  • count:=count + 1
• trả lại trước

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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

Đầu vào

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)

Đầu ra

1