Tổ tiên phổ biến thấp nhất của những chiếc lá sâu nhất trong Python

Giả sử chúng ta có một cây nhị phân gốc, chúng ta phải trả về tổ tiên chung thấp nhất của các lá sâu nhất của nó. Chúng tôi phải ghi nhớ rằng -

• Nút của cây nhị phân là nút lá nếu và chỉ khi nó không có nút con

• Độ sâu của gốc của cây là 0 và khi độ sâu của một nút là d, độ sâu của mỗi nút con của nó là d + 1.

• Tổ tiên chung thấp nhất của tập hợp S các nút trong nút A có độ sâu lớn nhất sao cho mọi nút trong S đều nằm trong cây con có gốc A.

Nếu đầu vào là [1,2,3,4,5],

thì đầu ra sẽ là [2,4,5]

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

• Xác định một phương thức có tên là giải quyết (), phương thức này sẽ sử dụng nút, phương thức này sẽ hoạt động như sau -

• nếu nút không có, thì trả về danh sách với [0, None]

• nếu các cây con bên trái và bên phải trống của nút, thì trả về một danh sách với [1, None]

• d1, l:=giải quyết (bên trái của nút), d2, r:=giải quyết (bên phải của nút)

• nếu d1> d2, thì trả về danh sách với các giá trị [d1 + 1, l]

• ngược lại khi d2> d1, thì trả về danh sách với các giá trị [d2 + 1, r]

• trả về một danh sách với các giá trị [d1 + 1, nút]

• Trong phương thức chính, chúng tôi sẽ thực hiện -

• danh sách:=giải quyết (gốc)

• danh sách trả lại [1]

Ví dụ (Python)

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
def print_tree(root):
   #print using inorder traversal
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def lcaDeepestLeaves(self, root):
      return self.solve(root)[1]
   def solve(self,node):
      if not node:
         return [0,None]
      if not node.left and not node.right:
         return [1,node]
      d1,l = self.solve(node.left)
      d2,r = self.solve(node.right)
      if d1>d2:
         return [d1+1,l]
      elif d2>d1:
         return [d2+1,r]
      return [d1+1,node]
ob = Solution()
root = make_tree([1,2,3,4,5])
print_tree(ob.lcaDeepestLeaves(root))

Đầu vào

[1,2,3,4,5]

Đầu ra

4, 2, 5,