Триплет с заданной суммой в BST | Комплект 2
Опубликовано: 23 Января, 2022
Учитывая двоичное дерево поиска и целое число X , задача состоит в том, чтобы найти, существует ли тройка с суммой X. Выведите « Да» или « Нет» соответственно. Обратите внимание, что три узла не обязательно могут быть разными.
Примеры:
Ввод: X = 15
5
/
3 7
/ /
2 4 6 8
Выход: Да
{5, 5, 5} - одна такая тройка.
{3, 5, 7}, {2, 5, 8}, {4, 5, 6} и другие.
Ввод: X = 16
1
2
3
4
5
Выход: Нет Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Простой подход: простой подход состоит в том, чтобы преобразовать BST в отсортированный массив, а затем найти триплет, используя три указателя. Это займет O (N) дополнительного места, где N - количество узлов, присутствующих в двоичном дереве поиска. Мы уже обсуждали подобную проблему в этой статье, для которой требуется O (N) лишнего места.
Лучший подход: мы решим эту проблему, используя метод экономии пространства, уменьшив сложность дополнительного пространства до O (H), где H - высота BST. Для этого мы будем использовать технику двух указателей на BST.
Мы пройдемся по всем узлам дерева один за другим, и для каждого узла мы попытаемся найти пару с суммой, равной (X - curr-> data), где 'curr' - текущий узел BST, которым мы являемся. прохождение.
Для поиска пары мы воспользуемся техникой, аналогичной описанной в этой статье.
Алгоритм: проходим каждый узел BST один за другим и для каждого узла:
- Создайте прямой и обратный итератор для BST. Скажем, значения узлов, на которые они указывают, - v1 и v2.
- Теперь на каждом шагу
- Если v1 + v2 = X, мы нашли пару, поэтому мы увеличим счет на 1.
- Если v1 + v2 меньше или равно x, мы заставим итератор вперед указывать на следующий элемент.
- Если v1 + v2 больше x, мы заставим итератор в обратном направлении указывать на предыдущий элемент.
- Мы продолжим описанное выше, пока левый итератор не указывает на узел с большим значением, чем правый узел.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node of the binary treestruct node { int data; node* left; node* right; node(int data) { this->data = data; left = NULL; right = NULL; }};// Function that returns true if a pair exists// in the binary search tree with sum equal to xbool existsPair(node* root, int x){ // Iterators for BST stack<node *> it1, it2; // Initializing forward iterator node* c = root; while (c != NULL) it1.push(c), c = c->left; // Initializing backward iterator c = root; while (c != NULL) it2.push(c), c = c->right; // Two pointer technique while (it1.size() and it2.size()) { // Variables to store values at // it1 and it2 int v1 = it1.top()->data, v2 = it2.top()->data; // Base case if (v1 + v2 == x) return 1; if (v1 > v2) break; // Moving forward pointer if (v1 + v2 < x) { c = it1.top()->right; it1.pop(); while (c != NULL) it1.push(c), c = c->left; } // Moving backward pointer else { c = it2.top()->left; it2.pop(); while (c != NULL) it2.push(c), c = c->right; } } // Case when no pair is found return 0;}// Function that returns true if a triplet exists// in the binary search tree with sum equal to xbool existsTriplet(node* root, node* curr, int x){ // If current node is NULL if (curr == NULL) return 0; // Conditions for existence of a triplet return (existsPair(root, x - curr->data) || existsTriplet(root, curr->left, x) || existsTriplet(root, curr->right, x));}// Driver codeint main(){ node* root = new node(5); root->left = new node(3); root->right = new node(7); root->left->left = new node(2); root->left->right = new node(4); root->right->left = new node(6); root->right->right = new node(8); int x = 24; if (existsTriplet(root, root, x)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.io.*;import java.util.*;// Node of the binary treeclass Node{ int data; Node left, right; Node(int item) { data = item; left = right = null; }}class GFG{ static Node root; // Function that returns true if a pair exists // in the binary search tree with sum equal to x static boolean existsPair(Node root, int x) { // Iterators for BST Stack<Node> it1 = new Stack<Node>(); Stack<Node> it2 = new Stack<Node>(); // Initializing forward iterator Node c = root; while (c != null) { it1.push(c); c = c.left; } // Initializing backward iterator c = root; while (c != null) { it2.push(c); c = c.right; } // Two pointer technique while (it1.size() > 0 && it2.size() > 0) { // Variables to store values at // it1 and it2 int v1 = it1.peek().data; int v2 = it2.peek().data; // Base case if (v1 + v2 == x) { return true; } if (v1 > v2) { break; } // Moving forward pointer if (v1 + v2 < x) { c = it1.peek().right; it1.pop(); while (c != null) { it1.push(c); c = c.left; } } // Moving backward pointer else { c = it2.peek().left; it2.pop(); while(c != null) { it2.push(c); c = c.right; } } } // Case when no pair is found return false; } // Function that returns true if a triplet exists // in the binary search tree with sum equal to x static boolean existsTriplet(Node root, Node curr, int x ) { // If current node is NULL if(curr == null) { return false; } // Conditions for existence of a triplet return (existsPair(root, x - curr.data) || existsTriplet(root, curr.left, x) || existsTriplet(root, curr.right, x)); } // Driver code public static void main (String[] args) { GFG tree = new GFG(); tree.root = new Node(5); tree.root.left = new Node(3); tree.root.right = new Node(7); tree.root.left.left = new Node(2); tree.root.left.right = new Node(4); tree.root.right.left = new Node(6); tree.root.right.right = new Node(8); int x = 24; if (existsTriplet(root, root, x)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the approachclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# Function that returns true if a pair exists# in the binary search tree with sum equal to xdef existsPair(root, x): # Iterators for BST it1, it2 = [], [] # Initializing forward iterator c = root while (c != None): it1.append(c) c = c.left # Initializing backward iterator c = root while (c != None): it2.append(c) c = c.right # Two pointer technique while (len(it1) > 0 and len(it2) > 0): # Variables to store values at # it1 and it2 v1 = it1[-1].data v2 = it2[-1].data # Base case if (v1 + v2 == x): return 1 if (v1 > v2): break # Moving forward pointer if (v1 + v2 < x): c = it1[-1].right del it1[-1] while (c != None): it1.append(c) c = c.left # Moving backward pointer else: c = it2[-1].left del it2[-1] while (c != None): it2.append(c) c = c.right # Case when no pair is found return 0# Function that returns true if a triplet exists# in the binary search tree with sum equal to xdef existsTriplet(root, curr, x): # If current node is NULL if (curr == None): return 0 # Conditions for existence of a triplet return (existsPair(root, x - curr.data) or existsTriplet(root, curr.left, x) or existsTriplet(root, curr.right, x))# Driver codeif __name__ == "__main__": root = Node(5) root.left = Node(3) root.right = Node(7) root.left.left = Node(2) root.left.right = Node(4) root.right.left = Node(6) root.right.right = Node(8) x = 24 if (existsTriplet(root, root, x)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;// Node of the binary treeclass Node{ public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}class GFG{ static Node root;// Function that returns true if a pair exists// in the binary search tree with sum equal to xstatic bool existsPair(Node root, int x){ // Iterators for BST Stack<Node> it1 = new Stack<Node>(); Stack<Node> it2 = new Stack<Node>(); // Initializing forward iterator Node c = root; while (c != null) { it1.Push(c); c = c.left; } // Initializing backward iterator c = root; while (c != null) { it2.Push(c); c = c.right; } // Two pointer techniqueРЕКОМЕНДУЕМЫЕ СТАТЬИ |