د محدود اضافي ځای سره دوه BSTs ضم کړئ


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د ګوګل د Microsoft پیرو یو über
د بائنری لټون ونه دوهم ونې ونې

ستونزه بیان

ستونزه "د محدود اضافي ځای سره دوه BSTs ضم کړئ" وايي چې تاسو ته دوه ورکړل شوي دوه لمبري پلټنه(BST) او تاسو اړتیا لرئ د دواړه ونو څخه عناصر په ترتیب سره چاپ کړئ. دا په داسې ترتیب کې دی چې داسې ښکاري چې عناصر د یو واحد BST څخه دي.

بېلګه

ننوتۍ

د محدود اضافي ځای سره دوه BSTs ضم کړئ

Output

د محدود اضافي ځای سره دوه BSTs ضم کړئ

4 5 6 7 9 13

توضیحي: نوی درخت چې د دواړه آخذې ونو یوځای کولو لخوا رامینځته شوی په عکس کې ښودل شوی. د پایلې لرونکي ونې داخلي تیریدونکی محصول ورکوي.

د محدود اضافي ځای سره دوه BSTs ضم کولو ته لاره

ستونزه "د محدود اضافي اضافي ځای سره دوه BSTs ضم کړئ" له موږ څخه غوښتنه کوي چې د یوځای شوي ونې انډر ټراورسال چاپ کړي. یوځای شوی ونې به د ورکړل شوي دوه ونو په یوځای کولو سره رامینځته شي. پدې توګه موږ به هڅه وکړو چې ورکړل شوي ونې ضمیمه کړو. مګر که موږ ونې سره یوځای کړو نو دا خورا ډیر سر ته اړتیا لري. د مستقیم یوځای کولو پرځای ، موږ کولی شو شاوخوا شاوخوا ځینې نورې لارې فکر وکړو. ځکه چې موږ یوازې اړتیا لرو په دواړه ورکړل شوي ونو کې په ترتیب شوي ب inه د نوډونو ارزښتونه چاپ کړو.

د دې حلولو لپاره به موږ هڅه وکړو چې په ګډه د دواړو ونو په اوږدو کې د بائنري لټون ونې تعقیبي انډر ټرورسال چلولو. دا کیدی شي که چیرې موږ پرمخ لاړ شو داخلي غځېدنه. او د انډر ټریورسال په دواړو نوډونو کې ارزښت پرتله کړئ. بیا به موږ دوه څخه کوچني چاپ کړو او لوی نوډ به په سټیک کې فشار ورکړو (هغه سټیک چې د تیریدونکي انډر ټریورسال په جریان کې کارول کیږي). هرکله چې موږ د یوې ونې سره ترسره شو ، نو موږ به په ساده ډول د ونې په اوږدو کې داخلي تعقیب له نوډونو سره پاتې شو.

کوډ

د محدود اضافي ځای سره دوه BSTs ضم کولو لپاره C ++ کوډ

#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

د اضافی محدود ځای سره دوه BSTs ضم کولو لپاره جاوا کوډ

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) ، په رسمي ډول د ځای پیچلتیا به د دواړو ونو د قد اندازه وي. مګر په بدترین حالت کې ، ننوت کیدی شي ونې سککی شي او پدې حالت کې ، قد به په ونو کې د نوډونو سره مساوي وي.