数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学在 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)
输出
Size: 3 Tree: 5, 3, 6,
698 次浏览
