数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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,
更新于： 2020年8月27日
227 次查看
广告