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

则输出为 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,
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

