資料結構
網路
關係資料庫管理系統 (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 次瀏覽
