資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學在 Python 中查詢具有相同左右子樹的最大子樹
假設我們有一個二叉樹；我們必須找到具有相同左右子樹的最大子樹。首選時間複雜度為 O(n)。
因此，如果輸入類似於
則輸出將為
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 solve()。這將接收根節點、編碼、最大大小、最大節點作為引數。
如果根節點為 None，則
返回 0
left_list := 包含空字串的列表
right_list := 包含空字串的列表
ls := solve(root.left, left_list, maxSize, maxNode)
rs := solve(root.right, right_list, maxSize, maxNode)
size := ls + rs + 1
如果 left_list[0] 與 right_list[0] 相同，則
如果 size > maxSize[0]，則
maxSize[0] := size
maxNode[0] := root
encode[0] := encode[0] 連線 "|" 連線 left_list[0] 連線 "|"
encode[0] := encode[0] 連線 "|" 連線 str(root.data) 連線 "|"
encode[0] := encode[0] 連線 "|" 連線 right_list[0] 連線 "|"
返回 size
從主方法中執行以下操作：
maximum := [0]
encode := 包含空字串的列表
solve(node, encode, maximum, maxNode)
返回 maximum
示例
讓我們看看以下實現以更好地理解：
class TreeNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
if (root == None):
return 0
left_list = [""]
right_list = [""]
ls = solve(root.left, left_list, maxSize, maxNode)
rs = solve(root.right, right_list, maxSize, maxNode)
size = ls + rs + 1
if (left_list[0] == right_list[0]):
if (size > maxSize[0]):
maxSize[0] = size
maxNode[0] = root
encode[0] = encode[0] + "|" + left_list[0] + "|"
encode[0] = encode[0] + "|" + str(root.data) + "|"
encode[0] = encode[0] + "|" + right_list[0] + "|"
return size
def largestSubtree(node, maxNode):
maximum = [0]
encode = [""]
solve(node, encode, maximum,maxNode)
return maximum
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree",maxNode[0].data)
print("and its size is ", maximum)輸入
root = TreeNode(55) root.left = TreeNode(15) root.right = TreeNode(70) root.left.left = TreeNode(10) root.left.right = TreeNode(25) root.right.left = TreeNode(75) root.right.left.left = TreeNode(65) root.right.left.right = TreeNode(80) root.right.right = TreeNode(75) root.right.right.left = TreeNode(65) root.right.right.right = TreeNode(80)
輸出
Root of largest sub-tree 70 and its size is [7]
更新於: 2020年8月25日
84 次檢視
廣告