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

假设我们有一个给定的二叉树；我们必须找到该给定二叉树中最大的完美子树的大小。众所周知，完美二叉树是指所有内部节点都有两个子节点且所有叶子节点都在同一级别的二叉树。

因此，如果输入如下所示：

则输出将为 3，子树为：

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

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

  • 定义一个名为 get_prefect_subtree() 的函数，它接受 root 作为参数

  • 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

    • 设置 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)

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

Size: 3
Tree: 5, 3, 6,

更新于：2020年8月20日

698 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告