मान लीजिए हमारे पास आकार n की एक सॉर्टेड लिंक्ड लिस्ट है, हमें एक बाइनरी सर्च ट्री बनाना है जिसमें k = floor(n/2) वें सबसे छोटे तत्व को रूट बनाया जाए। फिर बाएं सबट्री को kवें नोड के बाएं लिंक्ड लिस्ट से रिकर्सिवली बनाएं, और दाएं सबट्री को kवें नोड के दाएं लिंक्ड लिस्ट से रिकर्सिवली बनाएं।
उदाहरण के लिए, यदि इनपुट [2,4,5,7,10,15] है, तो आउटपुट निम्न ट्री होगा:
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
solve()मेथड परिभाषित करें जोnodeलेता है।यदि
nodenull है, तो null लौटाएं।यदि
node.nextnull है, तोnode.valके साथ एक नया ट्री नोड लौटाएं।slow := node,fast := node,prev := None।जब तक
fastऔरfast.nextnull नहीं हैं:prev := slowslow := slow.nextfast := fast.next.next
prev.next := None(लिस्ट को दो भागों में विभाजित करें)।root := TreeNode(slow.val)बनाएं।root.left := solve(node)(बाएं भाग)।root.right := solve(slow.next)(दाएं भाग)।rootलौटाएं।
उदाहरण
class ListNode: def __init__(self, data, next = None): self.val = data self.next = next class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution: def solve(self, node): if not node: return None if not node.next: return TreeNode(node.val) slow = fast = node prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = None root = TreeNode(slow.val) root.left = self.solve(node) root.right = self.solve(slow.next) return root ob = Solution() head = make_list([2,4,5,7,10,15]) root = ob.solve(head) print_tree(root)
इनपुट
[2,4,5,7,10,15]
आउटपुट
2, 4, 5, 7, 10, 15,
