Узлы из данных двух BST с суммой, равной X

Опубликовано: 23 Января, 2022

Учитывая два бинарных дерева поиска и целое число X , задача состоит в том, чтобы найти пару узлов, один из которых принадлежит первому BST, а второй - другому, так что их сумма равна X. Если такая пара существует, выведите Yes, иначе выведите No.

Примеры:

 Ввод: X = 100
BST 1:
          5 
        /  
       3 7 
      /  /  
     2 4 6 8
BST 2:
     11
      
       13
Выход: Нет
Такой пары с заданным значением нет.

Ввод: X = 16
BST 1:
          5 
        /  
       3 7 
      /  /  
     2 4 6 8
BST 2:
     11
      
       13
Выход: Да
5 + 11 = 16
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: мы решим эту проблему, используя подход с двумя указателями.
Мы создадим прямой итератор для первого BST и обратный - для второго. Таким образом, мы будем поддерживать прямой и обратный итераторы, которые будут выполнять итерацию BST в порядке обхода по порядку и в обратном порядке соответственно.

  1. Создайте прямой и обратный итераторы для первого и второго BST соответственно. Скажем, значения узлов, на которые они указывают, - v1 и v2.
  2. Теперь на каждом шагу
    • Если v1 + v2 = X, мы нашли пару.
    • Если v1 + v2 меньше или равно x, мы заставим итератор вперед указывать на следующий элемент.
    • Если v1 + v2 больше x, мы заставим итератор в обратном направлении указывать на предыдущий элемент.
  3. Мы продолжим описанное выше, пока оба итератора указывают на действительный узел.

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 tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function that returns true if a pair
// with given sum exists in the given BSTs
bool existsPair(node* root1, node* root2, int x)
{
    // Stack to store nodes for forward and backward
    // iterator
    stack<node *> it1, it2;
 
    // Initializing forward iterator
    node* c = root1;
    while (c != NULL)
        it1.push(c), c = c->left;
 
    // Initializing backward iterator
    c = root2;
    while (c != NULL)
        it2.push(c), c = c->right;
 
    // Two pointer technique
    while (it1.size() and it2.size()) {
 
        // To store the value of the nodes
        // current iterators are pointing to
        int v1 = it1.top()->data, v2 = it2.top()->data;
 
        // If found a valid pair
        if (v1 + v2 == x)
            return true;
 
        // Moving forward iterator
        if (v1 + v2 < x) {
            c = it1.top()->right;
            it1.pop();
            while (c != NULL)
                it1.push(c), c = c->left;
        }
 
        // Moving backward iterator
        else {
            c = it2.top()->left;
            it2.pop();
            while (c != NULL)
                it2.push(c), c = c->right;
        }
    }
 
    // If no such pair found
    return false;
}
 
// Driver code
int main()
{
 
    // First BST
    node* root1 = new node(11);
    root1->right = new node(15);
 
    // Second BST
    node* root2 = new node(5);
    root2->left = new node(3);
    root2->right = new node(7);
    root2->left->left = new node(2);
    root2->left->right = new node(4);
    root2->right->left = new node(6);
    root2->right->right = new node(8);
 
    int x = 23;
 
    if (existsPair(root1, root2, x))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Node of the binary tree
static class node
{
    int data;
    node left;
    node right;
    node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
// Function that returns true if a pair
// with given sum exists in the given BSTs
static boolean existsPair(node root1, node root2, int x)
{
    // Stack to store nodes for forward and backward
    // iterator
    Stack<node> it1 = new Stack(), it2 = new Stack();
 
    // Initializing forward iterator
    node c = root1;
    while (c != null)
    {
        it1.push(c);
        c = c.left;
    }
    // Initializing backward iterator
    c = root2;
    while (c != null)
    {
        it2.push(c);
        c = c.right;
    }
 
    // Two pointer technique
    while (it1.size() > 0 && it2.size() > 0)
    {
 
        // To store the value of the nodes
        // current iterators are pointing to
        int v1 = it1.peek().data, v2 = it2.peek().data;
 
        // If found a valid pair
        if (v1 + v2 == x)
            return true;
 
        // Moving forward iterator
        if (v1 + v2 < x)
        {
            c = it1.peek().right;
            it1.pop();
            while (c != null)
            {
                it1.push(c); c = c.left;
            }
        }
 
        // Moving backward iterator
        else
        {
            c = it2.peek().left;
            it2.pop();
            while (c != null)
            {
                it2.push(c); c = c.right;
            }
        }
    }
 
    // If no such pair found
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    // First BST
    node root1 = new node(11);
    root1.right = new node(15);
 
    // Second BST
    node root2 = new node(5);
    root2.left = new node(3);
    root2.right = new node(7);
    root2.left.left = new node(2);
    root2.left.right = new node(4);
    root2.right.left = new node(6);
    root2.right.right = new node(8);
 
    int x = 23;
 
    if (existsPair(root1, root2, x))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 implementation of the approach
 
# Node of the binary tree
class node:
     
    def __init__ (self, key):
         
        self.data = key
        self.left = None
        self.right = None
 
# Function that returns true if a pair
# with given sum exists in the given BSTs
def existsPair(root1, root2, x):
     
    # Stack to store nodes for forward
    # and backward iterator
    it1, it2 = [], []
 
    # Initializing forward iterator
    c = root1
    while (c != None):
        it1.append(c)
        c = c.left
 
    # Initializing backward iterator
    c = root2
    while (c != None):
        it2.append(c)
        c = c.right
 
    # Two pointer technique
    while (len(it1) > 0 and len(it2) > 0):
 
        # To store the value of the nodes
        # current iterators are pointing to
        v1 = it1[-1].data
        v2 = it2[-1].data
 
        # If found a valid pair
        if (v1 + v2 == x):
            return True
 
        # Moving forward iterator
        if (v1 + v2 < x):
            c = it1[-1].right
            del it1[-1]
             
            while (c != None):
                it1.append(c)
                c = c.left
 
        # Moving backward iterator
        else:
            c = it2[-1].left
            del it2[-1]
             
            while (c != None):
                it2.append(c)
                c = c.right
 
    # If no such pair found
    return False
 
# Driver code
if __name__ == "__main__":
 
    # First BST
    root1 = node(11)
    root1.right = node(15)
 
    # Second BST
    root2 = node(5)
    root2.left = node(3)
    root2.right = node(7)
    root2.left.left = node(2)
    root2.left.right = node(4)
    root2.right.left = node(6)
    root2.right.right = node(8)
 
    x = 23
 
    if (existsPair(root1, root2, x)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
     
class GFG
{
 
// Node of the binary tree
public class node
{
    public int data;
    public node left;
    public node right;
    public node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
// Function that returns true if a pair
// with given sum exists in the given BSTs
static bool existsPair(node root1, node root2, int x)
{
    // Stack to store nodes for forward and backward
    // iterator
    Stack<node> it1 = new Stack<node>(), it2 = new Stack<node>();
 
    // Initializing forward iterator
    node c = root1;
    while (c != null)
    {
        it1.Push(c);
        c = c.left;
    }
     
    // Initializing backward iterator
    c = root2;
    while (c != null)
    {
        it2.Push(c);
        c = c.right;
    }
 
    // Two pointer technique
    while (it1.Count > 0 && it2.Count > 0)
    {
 
        // To store the value of the nodes
        // current iterators are pointing to
        int v1 = it1.Peek().data, v2 = it2.Peek().data;
 
        // If found a valid pair
        if (v1 + v2 == x)
            return true;
 
        // Moving forward iterator
        if (v1 + v2 < x)
        {
            c = it1.Peek().right;
            it1.Pop();
            while (c != null)
            {
                it1.Push(c); c = c.left;
            }
        }
 
        // Moving backward iterator
        else
        {
            c = it2.Peek().left;
            it2.Pop();
            while (c != null)
            {
                it2.Push(c); c = c.right;
            }
        }
    }
 
    // If no such pair found
    return false;
}
 
// Driver code
public static void Main(String[] args)
{
    // First BST
    node root1 = new node(11);
    root1.right = new node(15);
 
    // Second BST
    node root2 = new<
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022