Рубрики

Найти пары с заданной суммой, такие, что парные элементы лежат в разных BST

Даны два дерева двоичного поиска (BST) и заданная сумма. Задача состоит в том, чтобы найти пары с заданной суммой, чтобы каждая пара элементов находилась в разных BST.

Примеры:

Input : sum = 10
     8                    5
   /   \                /   \
  3     10             2    18
 /  \      \         /   \  
1    6      14      1     3
    / \     /              \  
   5   7   13              4          
Output : (5,5), (6,4), (7,3), (8,2)
In above pairs first element lies in first
BST and second element lies in second BST

Простое решение этой проблемы — сохранить обход Inorder одного дерева во вспомогательном массиве, затем выбрать элемент один за другим из массива и найти его пару в другом дереве для заданной суммы. Временная сложность для этого подхода будет O (n 2 ), если общее количество узлов в обоих деревьях равны.

Эффективным решением для этого решения является хранение обходов Inorder обоих BST в двух разных вспомогательных массивах vect1 [] и vect2 []. Теперь мы следуем method1 этой статьи. Поскольку обход Inorder BST всегда дает отсортированную последовательность, нам не нужно сортировать наши массивы.

  • Возьмите итератор влево и направьте его в левый угол vect1 [].
  • Возьмите итератор вправо и направьте его в правый угол vect2 [].
  • Теперь, если vect11 [left] + vect2 [right] <sum, переместите левый итератор в vect1 [] в прямом направлении, т.е. левый ++ .
  • Теперь, если vect1 [left] + vect2 [right]> sum, переместите правый итератор в vect [] в обратном направлении, т.е. прямо — .

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска пар с заданной суммой таких
// что один элемент пары существует в одном BST и
// другое в другом BST.
#include<bits/stdc++.h>

using namespace std;

  
// двоичный узел дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST
// с указанным ключом

struct Node* newNode(int num)

{

    struct Node* temp = new Node;

    temp->data = num;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Утилита для вставки заданного ключа в BST

Node* insert(Node* root, int key)

{

    if (root == NULL)

        return newNode(key);

    if (root->data > key)

        root->left = insert(root->left, key);

    else

        root->right = insert(root->right, key);

    return root;

}

  
// храним обход storeInorder во вспомогательном массиве

void storeInorder(Node *ptr, vector<int> &vect)

{

    if (ptr==NULL)

        return;

    storeInorder(ptr->left, vect);

    vect.push_back(ptr->data);

    storeInorder(ptr->right, vect);

}

  
// Функция для поиска пары для данной суммы в разных BST
// vect1 [] -> хранит storeInorder обход первого bst
// vect2 [] -> хранит storeInorder обход второго bst

void pairSumUtil(vector<int> &vect1, vector<int> &vect2,

                                                int sum)

{

    // Инициализируем два индекса в два разных угла

    // из двух векторов.

    int left = 0;

    int right = vect2.size() - 1;

  

    // найти пару, сдвинув два угла.

    while (left < vect1.size() && right >= 0)

    {

        // Если мы нашли пару

        if (vect1[left] + vect2[right] == sum)

        {

            cout << "(" << vect1[left] << ", "

                 << vect2[right] << "), ";

            left++;

            right--;

        }

  

        // Если сумма больше, перейти к более высокому значению в

        // первый вектор.

        else if (vect1[left] + vect2[right] < sum)

            left++;

  

        // Если сумма меньше, перейти к меньшему значению в

        // второй вектор.

        else

            right--;

    }

}

  
// Печатает все пары с заданной суммой, так что
// элемент пары находится в дереве с root1 и другим
// узел находится в дереве с root2.

void pairSum(Node *root1, Node *root2, int sum)

{

    // Сохраняем обходы порядка двух BST в двух

    // векторы.

    vector<int> vect1, vect2;

    storeInorder(root1, vect1);

    storeInorder(root2, vect2);

  

    // Теперь проблема сводится к поиску пары

    // с заданной суммой такой, что один элемент находится в

    // vect1 и другие находятся в vect2.

    pairSumUtil(vect1, vect2, sum);

}

  
// Драйвер программы для запуска дела

int main()

{

    // первый BST

    struct Node* root1 = NULL;

    root1 = insert(root1, 8);

    root1 = insert(root1, 10);

    root1 = insert(root1, 3);

    root1 = insert(root1, 6);

    root1 = insert(root1, 1);

    root1 = insert(root1, 5);

    root1 = insert(root1, 7);

    root1 = insert(root1, 14);

    root1 = insert(root1, 13);

  

    // второй BST

    struct Node* root2 = NULL;

    root2 = insert(root2, 5);

    root2 = insert(root2, 18);

    root2 = insert(root2, 2);

    root2 = insert(root2, 1);

    root2 = insert(root2, 3);

    root2 = insert(root2, 4);

  

    int sum = 10;

    pairSum(root1, root2, sum);

  

    return 0;

}

Джава

// Java программа для поиска пар с заданной суммой
// что один элемент пары существует в одном BST и
// другое в другом BST.

import java.util.*;

class solution

{

   
// двоичный узел дерева

static class Node

{

    int data;

     Node left, right;

};

   
// Вспомогательная функция для создания нового узла BST
// с указанным ключом

static Node newNode(int num)

{

     Node temp = new Node();

    temp.data = num;

    temp.left = temp.right = null;

    return temp;

}

   
// Утилита для вставки заданного ключа в BST

static Node insert(Node root, int key)

{

    if (root == null)

        return newNode(key);

    if (root.data > key)

        root.left = insert(root.left, key);

    else

        root.right = insert(root.right, key);

    return root;

}

   
// храним обход storeInorder во вспомогательном массиве

static void storeInorder(Node ptr, Vector<Integer> vect)

{

    if (ptr==null)

        return;

    storeInorder(ptr.left, vect);

    vect.add(ptr.data);

    storeInorder(ptr.right, vect);

}

   
// Функция для поиска пары для данной суммы в разных BST
// vect1.get () -. store storeInorder обход первого BST
// vect2.get () -. store storeInorder обход второго BST

static void pairSumUtil(Vector<Integer> vect1, Vector<Integer> vect2,

                                                int sum)

{

    // Инициализируем два индекса в два разных угла

    // двух векторов

    int left = 0;

    int right = vect2.size() - 1;

   

    // найти пару, сдвинув два угла.

    while (left < vect1.size() && right >= 0)

    {

        // Если мы нашли пару

        if (vect1.get(left) + vect2.get(right) == sum)

        {

            System.out.print( "(" +vect1.get(left) + ", "+ vect2.get(right) + "), ");

            left++;

            right--;

        }

   

        // Если сумма больше, перейти к более высокому значению в

        // первый вектор.

        else if (vect1.get(left) + vect2.get(right) < sum)

            left++;

   

        // Если сумма меньше, перейти к меньшему значению в

        // второй вектор.

        else

            right--;

    }

}

   
// Печатает все пары с заданной суммой, так что
// элемент пары находится в дереве с root1 и другим
// узел находится в дереве с root2.

static void pairSum(Node root1, Node root2, int sum)

{

    // Сохраняем обходы порядка двух BST в двух

    // Векторы.

    Vector<Integer> vect1= new Vector<Integer>(), vect2= new Vector<Integer>();

    storeInorder(root1, vect1);

    storeInorder(root2, vect2);

   

    // Теперь проблема сводится к поиску пары

    // с заданной суммой такой, что один элемент находится в

    // vect1 и другие находятся в vect2.

    pairSumUtil(vect1, vect2, sum);

}

   
// Драйвер программы для запуска дела

public static void  main(String args[])

{

    // первый BST

     Node root1 = null;

    root1 = insert(root1, 8);

    root1 = insert(root1, 10);

    root1 = insert(root1, 3);

    root1 = insert(root1, 6);

    root1 = insert(root1, 1);

    root1 = insert(root1, 5);

    root1 = insert(root1, 7);

    root1 = insert(root1, 14);

    root1 = insert(root1, 13);

   

    // второй BST

     Node root2 = null;

    root2 = insert(root2, 5);

    root2 = insert(root2, 18);

    root2 = insert(root2, 2);

    root2 = insert(root2, 1);

    root2 = insert(root2, 3);

    root2 = insert(root2, 4);

   

    int sum = 10;

    pairSum(root1, root2, sum);

}
}
// предоставлено Арнабом Кунду

python3

# Python3 программа для поиска пар с заданным
# сумма такая, что существует один элемент пары
# в одном BST и в другом BST.

  
# Полезная функция для создания нового
# BST узел с ключом с заданным номером

class newNode: 

  

    # Конструктор для создания нового узла

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  
# Полезная функция для вставки
# данный ключ к BST

def insert(root, key):

    if root == None

        return newNode(key) 

    if root.data > key: 

        root.left = insert(root.left, key) 

    else:

        root.right = insert(root.right, key) 

    return root

  
# store storeInorder обход в
# вспомогательный массив

def storeInorder(ptr, vect):

    if ptr == None:

        return

    storeInorder(ptr.left, vect) 

    vect.append(ptr.data) 

    storeInorder(ptr.right, vect)

  
# Функция найти пару для данного
# сумма в разных BST
# vect1 [] -> магазин storeInorder
№ первого BST
# vect2 [] -> магазин storeInorder
№ второго BST

def pairSumUtil(vect1, vect2, Sum):

      

    # Инициализировать два индекса до двух

    # разные углы двух списков.

    left = 0

    right = len(vect2) - 1

  

    # найти пару, сдвинув два угла.

    while left < len(vect1) and right >= 0:

          

        # Если мы нашли пару

        if vect1[left] + vect2[right] == Sum:

            print("(", vect1[left], ","

                       vect2[right], "),", end = " "

            left += 1

            right -= 1

  

        # Если сумма больше, переходите к более высокой

        # значение в первых списках.

        elif vect1[left] + vect2[right] < Sum

            left += 1

  

        # Если сумма меньше, двигайтесь вниз

        # значение во вторых списках.

        else:

            right -= 1

  
# Печатает все пары с заданной суммой, так что
# элемент пары находится в дереве с root1 и другими
# узел находится в дереве с root2.

def pairSum(root1, root2, Sum):

      

    # Хранить в порядке обхода

    # два BST в двух списках.

    vect1 = []

    vect2 = []

    storeInorder(root1, vect1) 

    storeInorder(root2, vect2) 

  

    # Теперь проблема сводится к поиску

    # пара с заданной суммой, такой что

    Элемент # находится в vect1, а другой - в vect2.

    pairSumUtil(vect1, vect2, Sum)

  
Код водителя

if __name__ == '__main__':

      

    # первый BST

    root1 = None

    root1 = insert(root1, 8

    root1 = insert(root1, 10)

    root1 = insert(root1, 3

    root1 = insert(root1, 6

    root1 = insert(root1, 1

    root1 = insert(root1, 5

    root1 = insert(root1, 7

    root1 = insert(root1, 14

    root1 = insert(root1, 13)

  

    # второй BST

    root2 = None

    root2 = insert(root2, 5

    root2 = insert(root2, 18

    root2 = insert(root2, 2

    root2 = insert(root2, 1

    root2 = insert(root2, 3

    root2 = insert(root2, 4

  

    Sum = 10

    pairSum(root1, root2, Sum)

  
# Этот код предоставлен PranchalK

C #

using System;

using System.Collections.Generic;

  
// C # программа для поиска пар с заданной суммой
// что один элемент пары существует в одном BST и
// другое в другом BST.

public class solution

{

  
// двоичный узел дерева

public class Node

{

    public int data;

     public Node left, right;

}

  
// Вспомогательная функция для создания нового узла BST
// с указанным ключом

public static Node newNode(int num)

{

     Node temp = new Node();

    temp.data = num;

    temp.left = temp.right = null;

    return temp;

}

  
// Утилита для вставки заданного ключа в BST

public static Node insert(Node root, int key)

{

    if (root == null)

    {

        return newNode(key);

    }

    if (root.data > key)

    {

        root.left = insert(root.left, key);

    }

    else

    {

        root.right = insert(root.right, key);

    }

    return root;

}

  
// храним обход storeInorder во вспомогательном массиве

public static void storeInorder(Node ptr, List<int> vect)

{

    if (ptr == null)

    {

        return;

    }

    storeInorder(ptr.left, vect);

    vect.Add(ptr.data);

    storeInorder(ptr.right, vect);

}

  
// Функция для поиска пары для данной суммы в разных BST
// vect1.get () -. store storeInorder обход первого BST
// vect2.get () -. store storeInorder обход второго BST

public static void pairSumUtil(List<int> vect1, List<int> vect2, int sum)

{

    // Инициализируем два индекса в два разных угла

    // двух векторов

    int left = 0;

    int right = vect2.Count - 1;

  

    // найти пару, сдвинув два угла.

    while (left < vect1.Count && right >= 0)

    {

        // Если мы нашли пару

        if (vect1[left] + vect2[right] == sum)

        {

            Console.Write("(" + vect1[left] + ", " + vect2[right] + "), ");

            left++;

            right--;

        }

  

        // Если сумма больше, перейти к более высокому значению в

        // первый вектор.

        else if (vect1[left] + vect2[right] < sum)

        {

            left++;

        }

  

        // Если сумма меньше, перейти к меньшему значению в

        // второй вектор.

        else

        {

            right--;

        }

    }

}

  
// Печатает все пары с заданной суммой, так что
// элемент пары находится в дереве с root1 и другим
// узел находится в дереве с root2.

public static void pairSum(Node root1, Node root2, int sum)

{

    // Сохраняем обходы порядка двух BST в двух

    // Векторы.

    List<int> vect1 = new List<int>(), vect2 = new List<int>();

    storeInorder(root1, vect1);

    storeInorder(root2, vect2);

  

    // Теперь проблема сводится к поиску пары

    // с заданной суммой такой, что один элемент находится в

    // vect1 и другие находятся в vect2.

    pairSumUtil(vect1, vect2, sum);

}

  
// Драйвер программы для запуска дела

public static void Main(string[] args)

{

    // первый BST

     Node root1 = null;

    root1 = insert(root1, 8);

    root1 = insert(root1, 10);

    root1 = insert(root1, 3);

    root1 = insert(root1, 6);

    root1 = insert(root1, 1);

    root1 = insert(root1, 5);

    root1 = insert(root1, 7);

    root1 = insert(root1, 14);

    root1 = insert(root1, 13);

  

    // второй BST

     Node root2 = null;

    root2 = insert(root2, 5);

    root2 = insert(root2, 18);

    root2 = insert(root2, 2);

    root2 = insert(root2, 1);

    root2 = insert(root2, 3);

    root2 = insert(root2, 4);

  

    int sum = 10;

    pairSum(root1, root2, sum);

}
}

  

  // Этот код предоставлен Shrikant13


Выход:

(5,5),(6,4),(7,3),(8,2)

Временная сложность: O (n)
Вспомогательное пространство: O (n)

У нас есть другой подход, оптимизированный для решения этой проблемы. Идея состоит в том, чтобы преобразовать bst в двусвязный список и применить вышеуказанный метод для двусвязного списка. См. Эту статью.

Временная сложность: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти пары с заданной суммой, такие, что парные элементы лежат в разных BST

0.00 (0%) 0 votes