Объединить два BST с ограниченным дополнительным пространством


Сложный уровень Жесткий
Часто спрашивают в Амазонка Google Microsoft PayU Uber
Двоичное дерево поиска Двоичное дерево дерево

Постановка задачи

В задаче «Объединить два BST с ограниченным дополнительным пространством» указано, что вам дается два бинарное дерево поиска(BST), и вам нужно распечатать элементы из обоих деревьев в отсортированном порядке. Это в таком порядке, что кажется, что элементы взяты из одного BST.

Пример

вход

Объединить два BST с ограниченным дополнительным пространством

Результат

Объединить два BST с ограниченным дополнительным пространством

4 5 6 7 9 13

Объяснение: Новое дерево, сформированное путем слияния обоих входных деревьев, показано на изображении. Обход результирующего дерева в неупорядоченном порядке дает результат.

Подход к объединению двух BST с ограниченным дополнительным пространством

Задача «Объединить два BST с ограниченным дополнительным пространством» требует от нас распечатать в порядке обхода объединенного дерева. Объединенное дерево будет сформировано путем объединения данных двух деревьев. Таким образом мы попробуем объединить данные деревья. Но если бы мы объединили деревья, это потребовало бы больших накладных расходов. Вместо прямого слияния мы можем подумать о другом. Поскольку нам нужно только распечатать значения узлов в обоих заданных деревьях в отсортированном виде.

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

Код:

Код C ++ для объединения двух BST с ограниченным дополнительным пространством

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *left;
    node *right;
};

// returns a new node with supplied data
node* create(int data)
{
    node *temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(node *root)
{
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void merge(node *root1, node *root2)
{
    stack<node*> s1;node* cur1 = root1;
    stack<node*> s2;node* cur2 = root2;
    //if first tree is empty, print second tree
    if(!root1){
        inorder(root2);
        return;
    }
    // if second tree is empty, print first tree
    if(!root2){
        inorder(root2);
        return;
    }
    // print the nodes which are not yet visited or visited but not printed
    while(cur1 != NULL || !s1.empty() || cur2 != NULL || !s2.empty())
    {
        // iterative inorder
        if(cur1 != NULL || cur2 != NULL)
        {
            // Reach the leftmost node of both BSTs and push ancestors of
            // leftmost nodes to stack s1 and s2 respectively
            if(cur1 != NULL)
            {
                s1.push(cur1);
                cur1 = cur1->left;
            }
            if (cur2 != NULL)
            {
                s2.push(cur2);
                cur2 = cur2->left;
            }
        }
        else
        {
            // if anyone of the tree's current node becomes Null
            // then we need to check if stack is empty
            if(s1.empty())
            {
                while(!s2.empty())
                {
                    cur2 = s2.top();s2.pop();
                    cur2->left = NULL;
                    inorder(cur2);
                }
                return;
            }
            if(s2.empty())
            {
                while(!s1.empty())
                {
                    cur1 = s1.top();s1.pop();
                    cur1->left = NULL;
                    inorder(cur1);
                }
                return;
            }

            // compare elements at the top of both stacks
            cur1 = s1.top();s1.pop();
            cur2 = s2.top();s2.pop();

            // print the smaller of the two and push the larger element into the corresponding stack
            if(cur1->data < cur2->data)
            {
                cout<<cur1->data<<" ";
                cur1 = cur1->right;
                s2.push(cur2);
                cur2 = NULL;
            }
            else
            {
                cout<<cur2->data<<" ";
                cur2 = cur2->right;
                s1.push(cur1);
                cur1 = NULL;
            }
        }
    }
}

int main()
{
    node *root1 = NULL, *root2 = NULL;
    //first tree
    root1 = create(5);
    root1->left = create(4);
    root1->right = create(13);

    //second tree
    root2 = create(7);
    root2->left = create(6);
    root2->right = create(9);

    // Print sorted nodes of both trees
    merge(root1, root2);

    return 0;
}
4 5 6 7 9 13

Код Java для объединения двух BST с ограниченным дополнительным пространством

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static int count;
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }
  
  static void inorder(node root)
  {
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }
  
  static void merge(node root1, node root2)
  {
      Stack<node> s1 = new Stack<>();node cur1 = root1;
      Stack<node> s2 = new Stack<>();node cur2 = root2;
      //if first tree is empty, print second tree
      if(root1 == null){
          inorder(root2);
          return;
      }
      // if second tree is empty, print first tree
      if(root2 == null){
          inorder(root1);
          return;
      }
      // print the nodes which are not yet visited or visited but not printed
      while(cur1 != null || s1.empty() == false || cur2 != null || s2.empty() == false)
      {
          if(cur1 != null || cur2 != null)
          {
              // Reach the leftmost node of both BSTs and push ancestors of
              // leftmost nodes to stack s1 and s2 respectively
              if(cur1 != null)
              {
                  s1.push(cur1);
                  cur1 = cur1.left;
              }
              if (cur2 != null)
              {
                  s2.push(cur2);
                  cur2 = cur2.left;
              }
          }
          else
          {
              // if anyone of the tree's current node becomes Null
              // then we need to check if stack is empty
              if(s1.empty() == true)
              {
                  while (s2.empty() == false)
                  {
                      cur2 = s2.pop();
                      cur2.left = null;
                      inorder(cur2);
                  }
                  return ;
              }
              if(s2.empty() == true)
              {
                  while (s1.empty() == false)
                  {
                      cur1 = s1.pop();
                      cur1.left = null;
                      inorder(cur1);
                  }
                  return ;
              }
  
              // compare elements at the top of both stacks
              cur1 = s1.pop();
              cur2 = s2.pop();
              
              // print the smaller of the two and push the larger element into the corresponding stack
              if (cur1.data < cur2.data)
              {
                  System.out.print(cur1.data+" ");
                  cur1 = cur1.right;
                  s2.push(cur2);
                  cur2 = null;
              }
              else
              {
                  System.out.print(cur2.data+" ");
                  cur2 = cur2.right;
                  s1.push(cur1);
                  cur1 = null;
              }
          }
      }
  }
  
  public static void main(String[] args)
  {
      node root1 = null;
      node root2 = null;
      //first tree
      root1 = create(5);
      root1.left = create(4);
      root1.right = create(13);
  
      //second tree
      root2 = create(7);
      root2.left = create(6);
      root2.right = create(9);
  
      // Print sorted nodes of both trees
      merge(root1, root2);
  }

}
4 5 6 7 9 13

Анализ сложности

Сложность времени

О (Н + М), потому что мы выполнили одновременный обход обоих деревьев. Во время обхода без порядка мы перебирали узлы обоих деревьев и, следовательно, линейную временную сложность.

Космическая сложность

О (Н + М), более формально сложность пространства будет суммой высот обоих деревьев. Но в худшем случае входными данными могут быть искаженные деревья, и в этом случае высота будет равна количеству узлов в деревьях.