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

pythonserver side programmingprogramming更新于 2025/9/30 8:12:17

假设我们有一棵给定的二叉树;我们必须找到给定二叉树中最大完美子树的大小。众所周知,完美二叉树是一种二叉树,其中所有内部节点都有两个子节点,并且所有叶子都处于相同的级别。

因此,如果输入如下

则输出为 3,子树为

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

  • 定义一个名为 RetType 的块,它将保存 isPerfect、height 和 rootTree,它们最初都是 0

  • 定义一个名为 get_prefect_subtree() 的函数,它将获取 root

  • r_type := a new 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

    • 设置 r_type 为完美

    • r_type.rootTree := root

    • 返回 r_type

  • 设置 r_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,

相关文章


有用资源