資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢給定二叉樹中是否存在BST
假設我們給定一棵二叉樹。我們需要找到樹中最大的子樹，該子樹是二叉搜尋樹 (BST)。我們返回 BST 的根節點。
因此，如果輸入類似於
則輸出將為 -
為了解決這個問題，我們將遵循以下步驟 -
- c := 0
- m := null
- 定義一個函式 recurse()。這將接收節點作為引數
- 如果節點不為空，則
- left_val := recurse(節點的左子節點)
- right_val := recurse(節點的右子節點)
- count := 負無窮大
- 如果 (node.left 與 null 相同 或 node.left.val <= node.val) 且 (node 的右子節點與 null 相同 或 node.val <= node.right.val)，則
- count := left_val + right_val + 1
- 如果 count > c，則
- c := count
- m := node
- 返回 count
- 返回 0
- 如果節點不為空，則
- recurse(根節點)
- 返回 m
示例
讓我們檢視以下實現以更好地理解 -
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 print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end = ', ')
print_tree(root.right)
def solve(root):
c, m = 0, None
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
recurse(root)
return m
tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))輸入
tree = make_tree([1, 4, 6, 3, 5]) print_tree(solve(tree))
輸出
3, 4, 5,
更新於: 2021年10月19日
124 次檢視
廣告