สมมติว่าเราได้รับต้นไม้ไบนารี เราต้องหา subtree ที่ใหญ่ที่สุดจากทรีที่เป็น binary search tree (BST) เราส่งคืนโหนดรูทของ BST
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ค :=0
- ม :=null
- กำหนดฟังก์ชัน recurse() นี่จะใช้โหนด
- ถ้าโหนดไม่เป็นโมฆะ
- left_val :=เรียกซ้ำ (ซ้ายของโหนด)
- right_val :=เรียกซ้ำ (ด้านขวาของโหนด)
- จำนวน :=ลบอินฟินิตี้
- ถ้า (node.left เหมือนกับ null หรือ node.left.val <=node.val) และ (ทางขวาของ node เหมือนกับ null หรือ node.val <=node.right.val) แล้ว
- นับ :=left_val + right_val + 1
- ถ้านับ> c แล้ว
- c :=นับ
- m :=โหนด
- จำนวนคืนสินค้า
- คืน 0
- ถ้าโหนดไม่เป็นโมฆะ
- เรียกซ้ำ(ราก)
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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,
