मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें सबसे बड़ा सबट्री (अधिकतम नोड्स के साथ) ढूंढना है जो बाइनरी सर्च ट्री हो।
उदाहरण के लिए, यदि इनपुट ट्री है:

तो आउटपुट होगा:

समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करेंगे:
- max_size := [0], max_node := [null]
- traverse(node) फंक्शन परिभाषित करें:
- यदि node null है, तो खाली लिस्ट लौटाएं
- left := traverse(node.left)
- right := traverse(node.right)
- lst := left + [node.val] + right
- यदि lst सॉर्टेड है:
- यदि max_size[0] < len(lst) है, तो max_size[0] := len(lst) और max_node[0] := node
- lst लौटाएं
- traverse(root) कॉल करें
- max_node[0] लौटाएं
पायथन कार्यान्वयन
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
class Solution:
def solve(self, root):
max_size = [0]
max_node = [None]
def traverse(node):
if not node:
return []
left = traverse(node.left)
right = traverse(node.right)
lst = left + [node.val] + right
if sorted(lst) == lst:
if max_size[0] < len(lst):
max_size[0] = len(lst)
max_node[0] = node
return lst
traverse(root)
return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))इनपुट
root = TreeNode(12) root.left = TreeNode(3) root.right = TreeNode(5) root.right.left = TreeNode(4) root.right.right = TreeNode(6)
आउटपुट
4, 5, 6,