मान लीजिए, हमें एक बाइनरी सर्च ट्री (BST) प्रदान किया गया है जिसमें पूर्णांक मान हैं, और एक संख्या 'total' है। हमें यह पता लगाना है कि क्या प्रदान किए गए BST में तीन तत्वों का कोई समूह है जहां तीन तत्वों का योग आपूर्ति किए गए 'total' मान के बराबर है।
तो, यदि इनपुट इस तरह है:
total = 12, तो आउटपुट True होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- temp_list := शून्य से आरंभ एक नई सूची
- ट्री को इनऑर्डर ट्रैवर्स करें और इसे temp_list में डालें
- i के लिए रेंज 0 से (temp_list का आकार - 2) तक, 1 से बढ़ाएं, करें
- left := i + 1
- right := temp_list का आकार - 1
- जब तक left < right, करें
- यदि temp_list[i] + temp_list[left] + temp_list[right] sum के समान है, तो
- True लौटाएं
- अन्यथा जब temp_list[i] + temp_list[left] + temp_list[right] < sum गैर-शून्य है, तो
- left := left + 1
- अन्यथा,
- right := right - 1
- यदि temp_list[i] + temp_list[left] + temp_list[right] sum के समान है, तो
- False लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
class TreeNode: def __init__(self, value): self.value = value self.right = None self.left = None def traverse_inorder(tree_root, inorder): if tree_root is None: return traverse_inorder(tree_root.left, inorder) inorder.append(tree_root.value) traverse_inorder(tree_root.right, inorder) def solve(tree_root, sum): temp_list = [0] traverse_inorder(tree_root, temp_list) for i in range(0, len(temp_list) - 2, 1): left = i + 1 right = len(temp_list) - 1 while(left < right): if temp_list[i] + temp_list[left] + temp_list[right] == sum: return True elif temp_list[i] + temp_list[left] + temp_list[right] < sum: left += 1 else: right -= 1 return False tree_root = TreeNode(5) tree_root.left = TreeNode(3) tree_root.right = TreeNode(7) tree_root.left.left = TreeNode(2) tree_root.left.right = TreeNode(4) tree_root.right.left = TreeNode(6) tree_root.right.right = TreeNode(8) print(solve(tree_root, 12))
इनपुट
tree_root = TreeNode(5) tree_root.left = TreeNode(3) tree_root.right = TreeNode(7) tree_root.left.left = TreeNode(2) tree_root.left.right = TreeNode(4) tree_root.right.left = TreeNode(6) tree_root.right.right = TreeNode(8) 12
आउटपुट
True
