ثنائي وڻ جي صحيح نظاري کي پرنٽ ڪيو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ قبول ڪريو ايڊوب Amazon MakeMyTrip جو آهي اسپيڊل
بائنري وڻ وڻن وڻ ٽرانسورس

مسئلي جو بيان

مسئلو ”بائنري وڻ جو صحيح نظارو پرنٽ ڪريو“ بيان ڪري ٿو ته توهان کي هڪ بائنري وڻ ڏنو ويو آهي. هاڻي توهان کي هن وڻ جو صحيح نظارو ڳولڻ جي ضرورت آهي. هتي ، بائنري وڻ جي صحيح نظر مان پهاڪي جو نقشو ڇپائڻ جو مطلب آهي جئين وڻ جڏهن صحيح طرف کان ڏٺو وڃي.

مثال

ثنائي وڻ جي صحيح نظاري کي پرنٽ ڪيو

2 7 4 6

وضاحت

جيڪڏهن توهان بائنري وڻ کي صحيح طرف سان مشاهدو ڪيو. اسان رڳو نوڊس ڏسي سگھون ٿا جيڪي ٻاھرين ۾ ڇپيل آھن. ڇاڪاڻ ته جوڙ 3 ۽ 5 7 ۽ 4 جي پٺيان hiddenڪيل آهن.

بائنري وڻ جو صحيح قول ڇا ڇپائڻ جي ويجهو

ھن مسئلي ۾ ، اسان کي صحيح نظر ڳولڻ جي ضرورت آھي بائنري وڻ. مسئلو ٻن طريقن کي استعمال ڪندي حل ڪري سگهجي ٿو. انهن مان هڪ قطار استعمال ڪئي ۽ ٻئي هڪ قطار کي استعمال ڪندي. اول ، اسان قطار کي استعمال ڪندي نقطه نظر تي بحث ڪنداسين. تنهن ڪري ، هڪ جو استعمال ڪندي مسئلو حل ڪرڻ پنگتي حيثيت رکي ٿو. اسان بائنري وڻ جي پاڙ کان شروع ڪريون ٿا. وڻ جي هر سطح لاءِ ، اسان قطار ۾ نوڊس کي رکڻ لاءِ رکون ٿا. ايندڙ سطح جي جوڙ کي محفوظ ڪرڻ لاءِ ، اسان کي هاڻوڪي سطح جي نوڊس تي لهڻو آهي. تنهنڪري جڏهن اسان موجوده ليول جي نوڊس مٿان گذري رهيا آهيون. اسان هن سطح تي آخري نوڊ پرنٽ ڪيون ٿا. جڏهن اسان وڻ کي اسان جي سا sideي طرف کان ڏٺو. اسان جو ئي نوڊ آهي جيڪو سطح تي اسان جو ڏس آهي. اهو رستو هڪ قطار کي استعمال ڪري ٿو جيڪا جڳهه وٺندي آهي.

اچو ته تڪرار استعمال ڪندي حل تي بحث ڪريون. حل ڏا similarو جھڙو آھي وڻ جي کاٻي ڏيک ڳولڻ. هن طريقي ۾. اسان بس ٺاھڻ واري وڻ جي ڇول جيان ٺاھيندا آھيون جيڪو انڊرورس ٽرورسل جي سامهون آھي. پر اسان هن سطح تي پڻ ٽريڪ ڪيا آهيون جيڪو اسان هن وقت آهي ۽ وڌ کان وڌ حاصل ڪيل سطح هاڻي تائين. جيئن اسين کاٻي سبٽيري کان اڳ سا theي سبارٽ ڏانهن وڃو. جڏهن ته اسان وڻ مان نئين ليول تي داخل ٿيندا آهيون. پهريون ڀيرو اسان سان ملندڙ سا encounterي جوڙ جوڙيو. تنهن ڪري اسان هميشه هڪ چڪاس رکون ٿا جيڪڏهن موجوده ليول وڌ کان وڌ ليول کان وڌيڪ آهي ، اسان نوڊ پرنٽ ڪيون. جيڪڏهن اسان ڪمپائلر اسٽيڪ جي ضرورت جي جڳهه تي غور نه ڪيو وڃي ته بهتر آهي. مسئلي لاءِ خلائي پيچيدگي انحصار آهي وڻ جي اوچائي تي جيڪڏهن اسان اهو سمجهون ٿا ته جڳهه ترتيب ڏيڻ واري اسٽيڪ طرفان ورتو ويو آهي.

ڪوڊ

بائنري وڻ جو صحيح نظارو ڇپائڻ لاءِ C ++ ڪوڊ

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

int main(){
  node *root = create(2);
  root->left = create(3);
  root->right = create(7);
  root->left->left = create(5);
  root->left->right =create(4);
  root->left->right->left = create(6);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

بائنري وڻ جي صحيح منظر ڇپائڻ لاءِ جاوا ڪوڊ

import java.util.*;

class node{
  int data;
  node left;
  node right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  public static void main(String[] args){
    node root = create(2);
    root.left = create(3);
    root.right = create(7);
    root.left.left = create(5);
    root.left.right =create(4);
    root.left.right.left = create(6);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، اسان وڻ ۾ رڳو نوڊس مٿان چڙهي رهيا آهيون. تنهنڪري جيڪڏهن وڻ ۾ اين نوڊس آهن ، الگورتھم کي انجام ڏيڻ لاءِ O (N) آپريشن ڪرڻ گهرجن.

خلائي پيچيدگي

اي (1). جيڪڏهن مرتب ڪندڙ اسٽيڪ طرفان استعمال ٿيندڙ جڳهه جو خيال نه رکيو وڃي ، ٻيو اي (ايڇ) جڳھ گهربل آهي.