Python에서 왼쪽 및 오른쪽 하위 트리가 동일한 가장 큰 하위 트리 찾기

바이너리 트리가 있다고 가정합니다. 왼쪽과 오른쪽 서브트리가 동일한 가장 큰 서브트리를 찾아야 합니다. 선호하는 시간 복잡도는 O(n)입니다.

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

그러면 출력은

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

• solve() 함수를 정의합니다. 루트, 인코딩, maxSize, maxNode

  를 사용합니다.

• 루트가 None이면

  • 0 반환

• left_list :=빈 문자열이 있는 목록

• right_list :=빈 문자열이 있는 목록

• ls :=해결(root.left, left_list, maxSize, maxNode)

• rs :=해결(root.right, right_list, maxSize, maxNode)

• 크기 :=ls + rs + 1

• left_list[0]이 right_list[0]과 같으면

  • 크기> maxSize[0]이면

    • maxSize[0] :=크기

    • maxNode[0] :=루트

• 인코딩[0] :=인코딩[0] "|" 연결 연결 left_list[0] 연결 "|"

• 인코딩[0] :=인코딩[0] "|" 연결 str(root.data) 연결 "|"

  연결

• 인코딩[0] :=인코딩[0] "|" 연결 연결 right_list[0] "|" 연결

• 반환 크기

• 기본 방법에서 다음을 수행하십시오 -

• 최대 :=[0]

• 인코딩 :=빈 문자열이 있는 목록

• 해결(노드, 인코딩, 최대, 최대 노드)

• 최대 반환

예시

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

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
   if (root == None):
      return 0
   left_list = [""]
   right_list = [""]
   ls = solve(root.left, left_list, maxSize, maxNode)
   rs = solve(root.right, right_list, maxSize, maxNode)
   size = ls + rs + 1
   if (left_list[0] == right_list[0]):
      if (size > maxSize[0]):
         maxSize[0] = size
         maxNode[0] = root
   encode[0] = encode[0] + "|" + left_list[0] + "|"
   encode[0] = encode[0] + "|" + str(root.data) + "|"
   encode[0] = encode[0] + "|" + right_list[0] + "|"

   return size

def largestSubtree(node, maxNode):
   maximum = [0]
   encode = [""]
   solve(node, encode, maximum,maxNode)
   return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree",maxNode[0].data)
print("and its size is ", maximum)

입력

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

출력

Root of largest sub-tree 70
and its size is [7]