मान लीजिए हमें एक बाइनरी ट्री दिया गया है। हमें ट्री से सबसे बड़े सबट्री का पता लगाना है जो कि बाइनरी सर्च ट्री (BST) है। हम BST का रूट नोड लौटाते हैं।
तो, अगर इनपुट पसंद है
तो आउटपुट होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- सी :=0
- एम:=शून्य
- एक फ़ंक्शन रिकर्स () को परिभाषित करें। यह नोड लेगा
- यदि नोड रिक्त नहीं है, तो
- बाएं_वल:=रिकर्स (नोड के बाएं)
- right_val :=recurse(नोड के दाएं)
- गिनती :=ऋणात्मक अनंतता
- अगर (नोड.लेफ्ट अशक्त या नोड.लेफ्ट.वैल <=नोड.वैल के समान है) और (नोड का दायां अशक्त या नोड के समान है। वैल <=नोड.राइट.वैल), तो
- गिनती:=लेफ्ट_वैल + राइट_वल + 1
- अगर गिनती> सी, तो
- सी :=गिनती
- एम:=नोड
- वापसी की संख्या
- वापसी 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,