Аб'яднайце дзве 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

Аналіз складанасці

Складанасць часу

O (N + M), таму што мы зрабілі адначасовы пераход па абодвух дрэвах. Падчас абходной развязкі мы перабралі вузлы абодвух дрэў і, такім чынам, лінейную складанасць часу.

Касмічная складанасць

O (N + M), больш фармальна складанасць прасторы будзе сумай вышыні абодвух дрэў. Але ў горшым выпадку ўвод можа быць перакошаным дрэвам, і ў гэтым выпадку вышыня будзе роўная колькасці вузлоў у дрэвах.