在 Python 中查找给定二叉树中最大的完全子树

假设我们有一个二叉树；我们必须找到此二叉树中最大完全子树的大小。众所周知，如果所有级别都已完全填充（可能除了最后一级），并且最后一级尽可能地向左填充键，则二叉树为完全二叉树。

因此，如果输入类似于

那么输出将是大小为 4，中序遍历将是 10、45、60、70。

为了解决这个问题，我们将遵循以下步骤：

• 定义返回类型，并带有一些参数，如 isComplete、isPerfect，这些参数最初为假，然后是 size 和 rootTree，size 最初为 0，rootTree 为 null。
• ret_type := returnType
• 如果根为 null，则
  • ret_type.isPerfect := True
  • ret_type.isComplete := True
  • ret_type.size := 0
  • ret_type.rootTree := None
  • 返回 ret_type
• left_tree := checkCompleteness(root.left)
• right_tree := checkCompleteness(root.right)
• 如果 (left_tree.isPerfect 为 True 且 right_tree.isComplete 为 True 且左右树的高度相同，则
  • ret_type.isComplete := True
  • ret_type.isPerfect := right_tree.isPerfect
  • ret_type.size := left_tree.size + right_tree.size + 1
  • ret_type.rootTree := root
  • 返回 ret_type
• 如果 (left_tree.isComplete 为 True 且 right_tree.isPerfect 为 True 且左右树的高度相同，则
  • ret_type.isComplete := True
  • ret_type.isPerfect := False
  • ret_type.size := left_tree.size + right_tree.size + 1
  • ret_type.rootTree := root
  • 返回 ret_type
• ret_type.isPerfect := False
• ret_type.isComplete := False
• ret_type.size := left_tree.size 和 right_tree.size 的最大值
• 如果 left_tree.size > right_tree.size，则
  • ret_type.rootTree := left_tree.rootTree
• 否则，
  • ret_type.rootTree := right_tree.rootTree
• 返回 ret_type

Python

让我们看看以下实现以获得更好的理解：

import math
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class returnType :
   def __init__(self):
      self.isPerfect = None
      self.isComplete = None
      self.size = 0
      self.rootTree = None
def getHeight(size):
   return int(math.ceil(math.log(size + 1)/math.log(2)))
def checkCompleteness(root) :
   ret_type = returnType()
   if (root == None):
      ret_type.isPerfect = True
      ret_type.isComplete = True
      ret_type.size = 0
      ret_type.rootTree = None
      return ret_type
   left_tree = checkCompleteness(root.left)
   right_tree = checkCompleteness(root.right)
   if (left_tree.isPerfect == True and right_tree.isComplete == True and getHeight(left_tree.size) == getHeight(right_tree.size)) :
      ret_type.isComplete = True
      ret_type.isPerfect = right_tree.isPerfect
      ret_type.size = left_tree.size + right_tree.size + 1
      ret_type.rootTree = root
      return ret_type
   if (left_tree.isComplete == True and right_tree.isPerfect == True and getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
      ret_type.isComplete = True
      ret_type.isPerfect = False
      ret_type.size = left_tree.size + right_tree.size + 1
      ret_type.rootTree = root
      return ret_type
      ret_type.isPerfect = False
      ret_type.isComplete = False
      ret_type.size =max(left_tree.size, right_tree.size)
      if(left_tree.size > right_tree.size ):
         ret_type.rootTree = left_tree.rootTree
      else:
         ret_type.rootTree = right_tree.rootTree
      return ret_type
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)
ans = checkCompleteness(root)
print( "Size:" , ans.size )
print("Inorder Traversal: ", end = '')
print_tree(ans.rootTree)

输入

root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

输出

Size: 4
Inorder Traversal: 10, 45, 60, 70,

Arnab Chakraborty

更新于： 2020年8月27日

227 次查看

开启你的 职业生涯

通过完成课程获得认证

开始