資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢給定二叉樹中最大BST的和值
假設我們提供了一個二叉樹。我們需要找出它子樹中是否存在二叉搜尋樹（BST），並找出最大BST的和。為了找出和，我們將該BST中每個節點的值加起來。我們將和值作為輸出返回。
所以，如果輸入如下所示：
那麼輸出將是12。
給定二叉樹中的BST為：
節點的和 = 12。
為了解決這個問題，我們將遵循以下步驟：
- c := 0
- m := null
- value := 0
- 定義一個函式recurse()。它將接收節點作為引數
- 如果節點不為空，則
- left_val := recurse(節點的左子節點)
- right_val := recurse(節點的右子節點)
- count := 負無窮大
- 如果（節點的左子節點為空或節點的左子節點的值 <= 節點的值）並且（（節點的右子節點為空或節點的值 <= 節點的右子節點的值），則
- count := left_val + right_val + 1
- 如果count > c，則
- c := count
- m := 節點
- 返回count
- 返回0
- 如果節點不為空，則
- 定義一個函式calculate_sum()。它將接收根節點作為引數
- 如果根節點不為空，則
- calculate_sum(根節點的左子節點)
- value := value + 根節點的值
- calculate_sum(根節點的右子節點)
- 如果根節點不為空，則
- recurse(根節點)
- calculate_sum(m)
- 返回value
示例
讓我們看看以下實現以獲得更好的理解：
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree= TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def solve(root):
c, m, value = 0, None, 0
def recurse(node):
if node:
nonlocal c, m
left_val = recurse(node.left)
right_val = recurse(node.right)
count = -float("inf")
if (node.left == None or node.left.val <= node.val) and (node.right == None or node.val <= node.right.val):
count = left_val + right_val + 1
if count > c:
c = count
m = node
return count
return 0
def calculate_sum(root):
nonlocal value
if root is not None:
calculate_sum(root.left)
value += root.val
calculate_sum(root.right)
recurse(root)
calculate_sum(m)
return value
tree = make_tree([1, 4, 6, 3, 5])
print(solve(tree))輸入
tree = make_tree([1, 4, 6, 3, 5]) print(solve(tree))
輸出
12
更新於: 2021年10月19日
172 次瀏覽
廣告