समस्या
मान लीजिए हमारे पास एक बाइनरी ट्री है, यह निर्धारित करें कि यह एक वैध बाइनरी सर्च ट्री (BST) है या नहीं। मान लें कि BST को इस प्रकार परिभाषित किया गया है:
- एक नोड का बायाँ उपट्री केवल उन नोड्स को रखता है जिनकी कुंजी नोड की कुंजी से छोटी होती है।
- एक नोड का दायाँ उपट्री केवल उन नोड्स को रखता है जिनकी कुंजी नोड की कुंजी से बड़ी होती है।
- बाएँ और दाएँ दोनों उपट्री भी बाइनरी सर्च ट्री होने चाहिए।
उदाहरण के लिए, यदि ट्री इस तरह है:
आउटपुट true होगा।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- solve() नामक एक पुनरावर्ती फ़ंक्शन बनाएं, यह रूट, मिन और मैक्स लेगा, विधि इस प्रकार होगी:
- यदि रूट null है, तो true लौटाएं
- यदि रूट का मान <= मिन या रूट का मान >= मैक्स, तो false लौटाएं
- (solve(रूट का बायाँ, मिन, रूट का मान) AND solve(रूट का दायाँ, रूट का मान, मैक्स)) लौटाएं
- प्रारंभ में solve() विधि को रूट, और -inf को मिन और inf को मैक्स के रूप में पास करके कॉल करें।
उदाहरण (Python):
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data 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 class Solution(object): def isValidBST(self, root): return self.solve(root,-1000000000000000000000,1000000000000000000000) def solve(self,root,min_val,max_val): if root == None or root.data == 0: return True if (root.data <= min_val or root.data >=max_val): return False return self.solve(root.left,min_val,root.data) and self.solve(root.right,root.data,max_val) ob1 = Solution() tree = make_tree([3,1,4,None,2,None,5]) print(ob1.isValidBST(tree)) tree = make_tree([5,1,4,None,None,3,6]) print(ob1.isValidBST(tree))
इनपुट
[3,1,4,null,2,null,5] [5,1,4,null,null,3,6]
आउटपुट
true false
