Chương trình tìm nút sâu nhất bên trái của cây bằng Python

Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm giá trị của nút sâu nhất. Nếu có nhiều hơn một nút sâu nhất, thì trả về nút sâu nhất ngoài cùng bên trái.

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

thì đầu ra sẽ là 4 vì 4 và 7 là sâu nhất nhưng 4 ở bên trái nhiều nhất.

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

• queue:=một hàng đợi có một nút gốc.

• left_max:=giá trị của root

• trong khi kích thước của hàng đợi> 0, thực hiện

  • level_size:=kích thước hàng đợi

  • đối với tôi trong phạm vi 0 đến level_size, hãy làm

    • temp:=phần tử đầu tiên từ hàng đợi và xóa nó

    • nếu tôi giống 0, thì

      • left_max:=giá trị của nhiệt độ

    • nếu bên trái của nhiệt độ là khác 0, thì

      • chèn bên trái của tạm thời vào cuối hàng đợi

    • nếu quyền tạm thời không rỗng, thì

      • chèn quyền tạm thời vào cuối hàng đợi

  • return left_max

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

Đầu vào

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)

Đầu ra

4