파이썬을 사용하여 주어진 노드의 이진 트리의 가장 낮은 공통 조상을 찾는 프로그램

이진 트리가 주어지고 트리에 있는 모든 노드의 가장 낮은 공통 조상을 찾으라는 요청을 받았다고 가정합니다. 이진 트리에서 가장 낮은 공통 조상은 노드 x1, x2, x3,...., xn이 자손인 가장 낮은 노드입니다. 특정 노드는 자체의 하위 노드일 수도 있습니다. 노드를 찾아서 출력으로 반환해야 합니다. 입력은 트리의 루트 노드와 조상을 찾아야 하는 노드 목록입니다.

따라서 입력이 다음과 같으면

조상을 찾아야 하는 노드 목록은 [6, 8]입니다. 그러면 출력은 7이 됩니다.

노드 6과 8이 하위 노드인 가장 낮은 노드가 7이기 때문에 출력은 7입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 함수 fn() 을 정의합니다. 노드가 필요합니다.

  • 노드가 null과 유사하면

    • 반환 노드

  • 그렇지 않으면 노드가 노드에 미리 설정되어 있으면

    • 반환 노드

  • 왼쪽 :=fn(노드의 왼쪽) ,

  • right :=fn(노드의 오른쪽)

  • 왼쪽과 오른쪽이 null이 아니면

    • 반환 노드

  • 그렇지 않으면

    • 왼쪽 또는 오른쪽이 null이 아니면

      • 반환 노드

• 노드 :=새 목록

• node_list의 각 요소에 대해 수행

  • 노드 끝에 search_node(root, elem) 삽입

• 노드 :=노드의 새 세트

• 반환 fn(루트)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

import collections
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 search_node(root, element):
   if (root == None):
      return None
   if (root.data == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
def solve(root, node_list):
   nodes = []
   for elem in node_list:
      nodes.append(search_node(root, elem))
      nodes = set(nodes)
def fn(node):
   if not node:
      return node
   elif node in nodes:
      return node
      left, right = fn(node.left), fn(node.right)
      return node if left and right else left or right
   return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6,8]).data)

입력

make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]

출력

7