Pythonで同じ左と右のサブツリーを持つ最大のサブツリーを検索します

したがって、入力が次のような場合

その場合、出力は次のようになります

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これはroot、encode、maxSize、maxNodeを取ります

• ルートがNoneの場合、

  • 0を返す

• left_list：=空白の文字列を含むリスト

• right_list：=空白の文字列を含むリスト

• ls：=resolve（root.left、left_list、maxSize、maxNode）

• rs：=resolve（root.right、right_list、maxSize、maxNode）

• サイズ：=ls + rs + 1

• left_list[0]がright_list[0]と同じ場合、

  • サイズ>maxSize[0]の場合、

    • maxSize [0]：=サイズ

    • maxNode [0]：=root

• encode [0]：=encode[0]連結"|" concatenate left_list [0] concatenate "|"

• encode [0]：=encode[0]連結"|" concatenate str（root.data）concatenate "|"

• encode [0]：=encode[0]連結"|" concatenate right_list [0] concatenate "|"

• 返品サイズ

• メインの方法から、次のようにします-

• 最大：=[0]

• ：=リストを空白の文字列でエンコードする

• 解決（ノード、エンコード、最大、maxNode）

• 最大値を返す

例

理解を深めるために、次の実装を見てみましょう-

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]