Количество пар с заданной суммой в дереве двоичного поиска

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

Учитывая дерево двоичного поиска и число X. Задача состоит в том, чтобы найти количество различных пар различных узлов в BST с суммой, равной X. Нет двух узлов с одинаковыми значениями.

Примеры:


Ввод: X = 5
          5 
        /  
       3 7 
      /  /  
     2 4 6 8    
Выход: 1
{2, 3} - единственная возможная пара. 
Таким образом, ответ равен 1.

Ввод: X = 6
      1
       
        2
         
          3
           
            4
             
              5
   
Выход: 2
Возможные пары: {{1, 5}, {2, 4}}.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход : идея состоит в том, чтобы хешировать все элементы BST или преобразовать BST в отсортированный массив. После этого найдите количество пар, используя приведенный здесь алгоритм.
Сложность времени: O (N).
Космическая сложность: O (N).

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

  1. Создайте итераторы прямого и обратного направления для BST. Предположим, что значения узлов, на которые они указывают, равны v 1 и v 2 соответственно.
  2. Теперь на каждом шагу
    • Если v 1 + v 2 = X, пара найдена, таким образом увеличьте счет на 1.
    • Если v 1 + v 2 меньше или равно x, мы сделаем прямой итератор точкой на следующий элемент.
    • Если v 1 + v 2 больше 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 Binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
  
// Function to find a pair
int cntPairs(node* root, int x)
{
    // Stack to store nodes for
    // forward and backward iterator
    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;
  
    // Variable to store final answer
    int ans = 0;
  
    // two pointer technique
    while (it1.top() != it2.top()) {
  
        // Variables to store the
        // value of the nodes current
        // iterators are pointing to.
        int v1 = it1.top()->data;
        int v2 = it2.top()->data;
  
        // If we find a pair
        // then count is increased by 1
        if (v1 + v2 == x)
            ans++;
  
        // 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;
        }
    }
  
    // Returning final answer
    return ans;
}
  
// Driver code
int main()
{
    /*    5 
        /    
       3     7 
      /    /  
     2   4 6   8 */
    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 = 10;
  
    cout << cntPairs(root, x);
  
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
  
class GFG
{
  
// Node of Binary tree
static class node
{
    int data;
    node left;
    node right;
    node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
  
// Function to find a pair
static int cntPairs(node root, int x)
{
    // Stack to store nodes for
    // forward and backward iterator
    Stack<node > it1 = new Stack<>();
    Stack<node > it2 = new Stack<>();
  
    // 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;
    }
      
    // Variable to store final answer
    int ans = 0;
  
    // two pointer technique
    while (it1.peek() != it2.peek()) 
    {
  
        // Variables to store the
        // value of the nodes current
        // iterators are pointing to.
        int v1 = it1.peek().data;
        int v2 = it2.peek().data;
  
        // If we find a pair
        // then count is increased by 1
        if (v1 + v2 == x)
            ans++;
  
        // 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;
            }
        }
    }
  
    // Returning final answer
    return ans;
}
  
// Driver code
public static void main(String[] args)
{
    /* 5 
        /  
    3     7 
    / /  
    2 4 6 8 */
    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 = 10;
  
    System.out.print(cntPairs(root, x));
}
}
  
// This code is contributed by Rajput-Ji

Python

# Python implementation of above algorithm
  
# Utility class to create a node 
class node: 
    def __init__(self, key): 
        self.data = key 
        self.left = self.right = None
  
# Function to find a pair
def cntPairs( root, x):
  
    # Stack to store nodes for
    # forward and backward iterator
    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
  
    # Variable to store final answer
    ans = 0
  
    # two pointer technique
    while (it1[-1] != it2[-1]) :
  
        # Variables to store the
        # value of the nodes current
        # iterators are pointing to.
        v1 = it1[-1].data
        v2 = it2[-1].data
  
        # If we find a pair
        # then count is increased by 1
        if (v1 + v2 == x):
            ans=ans+1
  
        # Moving forward iterator
        if (v1 + v2 <= x) :
            c = it1[-1].right
            it1.pop()
            while (c != None):
                it1.append(c)
                c = c.left
          
        # Moving backward iterator
        else :
            c = it2[-1].left
            it2.pop()
            while (c != None):
                it2.append(c)
                c = c.right
          
    # Returning final answer
    return ans
  
# Driver code
  
#         5 
#     /  
#     3     7 
#     / /  
#     2 4 6 8 
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 = 10
  
print(cntPairs(root, x))
  
# This code is contributed by Arnab Kundu

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
  
class GFG
{
  
// Node of 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 to find a pair
static int cntPairs(node root, int x)
{
    // Stack to store nodes for
    // forward and backward iterator
    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;
    }
      
    // Variable to store readonly answer
    int ans = 0;
  
    // two pointer technique
    while (it1.Peek() != it2.Peek()) 
    {
  
        // Variables to store the
        // value of the nodes current
        // iterators are pointing to.
        int v1 = it1.Peek().data;
        int v2 = it2.Peek().data;
  
        // If we find a pair
        // then count is increased by 1
        if (v1 + v2 == x)
            ans++;
  
        // 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;
Структуры данных

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

Различия между структурой данных массива и словаря
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