Տպեք Երկուական ծառի աջ տեսքը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Adobe Amazon MakeMyTrip- ը Snapdeal
Երկուական ծառ ծառ Reeառի անցում

Խնդիրի հայտարարություն

«Երկուական ծառի ճիշտ տեսք տպեք» խնդիրը նշում է, որ ձեզ տրվում է երկուական ծառ: Այժմ դուք պետք է գտնեք այս ծառի ճիշտ տեսքը: Այստեղ երկուական ծառի ճիշտ տեսքը նշանակում է տպել հաջորդականությունը, քանի որ ծառը նայում է, երբ նայում է ճիշտ ուղղությամբ:

Օրինակ

Տպեք Երկուական ծառի աջ տեսքը

2 7 4 6

բացատրություն

Եթե ​​դիտեք երկուական ծառը ճիշտ ուղղությամբ: Մենք ունակ ենք տեսնել միայն հանգույցները, որոնք տպված են արդյունքի մեջ: Քանի որ 3 և 5 հանգույցները թաքնվում են համապատասխանաբար 7-ի և 4-ի ետևում:

Երկուական ծառի ճիշտ տեսքը տպելու մոտեցում

Այս խնդրում մենք պետք է գտնենք ճիշտ տեսակետը երկուական ծառ, Խնդիրը կարելի է լուծել ՝ օգտագործելով երկու մոտեցում: Նրանցից մեկը հերթ է օգտագործում, իսկ մյուսը ՝ հետադարձ: Նախ, մենք կքննարկենք հերթը օգտագործելու մոտեցումը: Այսպիսով, խնդիրը լուծելու համար օգտագործելով a հերթ, Մենք սկսում ենք երկուական ծառի արմատից: Levelառի յուրաքանչյուր մակարդակի համար մենք շարունակում ենք հերթում պահել հանգույցները: Հաջորդ մակարդակի հանգույցները պահելու համար մենք պետք է անցնենք ընթացիկ մակարդակի հանգույցների վրայով: Այսպիսով, երբ մենք անցնում ենք ընթացիկ մակարդակի հանգույցների վրայով: Մենք այս մակարդակում տպում ենք վերջին հանգույցը: Երբ ծառը դիտում ենք աջ կողմից: Միակ հանգույցը, որը մեզ համար տեսանելի է, մակարդակի ամենաուղղակի հանգույցն է: Այս մոտեցումը օգտագործում է հերթեր, որոնք տարածություն են խլում:

Եկեք քննարկենք լուծումը `օգտագործելով ռեկուրսիան: Լուծումը շատ նման է ծառի ձախ տեսքը գտնելու լուծմանը: Այս մոտեցման մեջ: Մենք պարզապես կատարում ենք ծառի շրջանցում, որը հակառակն է անշարժ շրջադարձին: Բայց մենք նաև հետևում ենք այն մակարդակին, որը ներկայումս գտնվում ենք և մինչ այժմ ձեռք բերված առավելագույն մակարդակը: Երբ մենք շարժվում ենք դեպի աջ ենթածառ դեպի ձախ ենթածառ: Ամեն անգամ, երբ մենք ծառի մեջ նոր մակարդակ ենք մտնում: Մենք առաջին հերթին հանդիպում ենք ամենաանհրաժեշտ հանգույցին: Այսպիսով, մենք միշտ ստուգում ենք, եթե ընթացիկ մակարդակն ավելի մեծ է, քան առավելագույն մակարդակը, մենք տպում ենք հանգույցը: Մոտեցումն ավելի լավ է, եթե հաշվի չառնենք կազմողի բուրգի համար պահանջվող տարածությունը: Խնդրի տիեզերական բարդությունը կախված է ծառի բարձրությունից, եթե հաշվի առնենք կազմողի բուրգը վերցրած տարածությունը:

Կոդ

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

Java կոդ ՝ Երկուական ծառի ճիշտ տեսքը տպելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), մենք պարզապես անցնում ենք ծառի հանգույցների վրայով: Այսպիսով, եթե ծառի մեջ կան N հանգույցներ, ալգորիթմը պահանջում է O (N) գործողություններ կատարել:

Տիեզերական բարդություն

Ո (1) Եթե ​​կոմպիլյատորի բուրգի կողմից օգտագործված տարածքը հաշվի չի առնվում, այլապես Ո (Հ) տարածք է պահանջվում: