Pythonで特定の二分木で最大の完全なサブツリーを見つける

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

その場合、出力は3になり、サブツリーは

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

• RetTypeと呼ばれる1つのブロックを定義します。これは、isPerfect、height、rootTreeを保持し、最初はすべて0です

• get_prefect_subtree（）という関数を定義します。これはルートを取ります

• r_type：=新しいRetType

• rootがNoneと同じ場合、

  • r_type.isPerfect：=True

  • r_type.height：=0

  • r_type.rootTree：=null

  • r_typeを返す

• left_subtree：=get_prefect_subtree（root.left）

• right_subtree：=get_prefect_subtree（root.right）

• left_subtreeが完全で、right_subtreeが完全で、left_subtreeの高さがright_subtreeの高さと同じである場合、

  • r_typeの高さ：=left_subtreeの高さ+1

  • setr_typeは完璧です

  • r_type.rootTree：=root

  • r_typeを返す

• setr_typeは完全ではありません

• r_type.height：=left_subtreeの高さの最大値、right_subtreeの高さ

• left_subtreeの高さ>right_subtreeの高さの場合、

  • r_type.rootTree：=left_subtree.rootTree

• それ以外の場合

  • r_type.rootTree：=right_subtree.rootTree

• r_typeを返す

例

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class RetType:
   def __init__(self):
      isPerfect = 0
      height = 0
      rootTree = 0
def get_prefect_subtree(root):
   r_type = RetType()
   if (root == None) :
      r_type.isPerfect = True
      r_type.height = 0
      r_type.rootTree = None
      return r_type
   left_subtree = get_prefect_subtree(root.left)
   right_subtree = get_prefect_subtree(root.right)
   if (left_subtree.isPerfect and right_subtree.isPerfect and left_subtree.height == right_subtree.height) :
      r_type.height = left_subtree.height + 1
      r_type.isPerfect = True
      r_type.rootTree = root
      return r_type
   r_type.isPerfect = False
   r_type.height = max(left_subtree.height, right_subtree.height)
   if (left_subtree.height > right_subtree.height ):
      r_type.rootTree = left_subtree.rootTree
   else :
      r_type.rootTree = right_subtree.rootTree
   return r_type

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

res = get_prefect_subtree(root)
h = res.height

print ("Size: " , pow(2, h) - 1)
print ("Tree: ", end = " ")
print_tree(res.rootTree)

入力

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

出力

Size: 3
Tree: 5, 3, 6,