Эки дарактын туура көрүнүшүн басып чыгаруу  


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Adobe Amazon MakeMyTrip Snapdeal
Binary Tree дарак Tree Traversal

Маселени билдирүү  

"Эки дарактын туура көрүнүшүн басып чыгаруу" маселеси сизге экилик даракты бергенин билдирет. Эми бул бактын туура көрүнүшүн табышыңыз керек. Бул жерде экилик дарактын туура көрүнүшү, дарак туура багыттан каралса, ырааттуулукту басып чыгарууну билдирет.

мисал  

Эки дарактын туура көрүнүшүн басып чыгаруутөөнөч

2 7 4 6

түшүндүрүү

Эгер экилик бакты туура багытта байкасаңыз. Чыгууда басылып чыккан түйүндөрдү гана көрө алабыз. Себеби 3 жана 5 түйүндөрү тиешелүүлүгүнө жараша 7 жана 4 артынан катылып калат.

Эки дарактын туура көрүнүшүн басып чыгаруу ыкмасы  

Бул көйгөйдө биз туура көз карашты табышыбыз керек экилик дарак. Маселени эки ыкманы колдонуп чечсе болот. Алардын бири кезекти, экинчиси рекурсияны колдонот. Алгач, кезекти колдонуу ыкмасын талкуулайбыз. Ошентип, көйгөйдү чечүү үчүн кезек. Биз экилик дарактын тамырынан баштайбыз. Бактын ар бир деңгээли үчүн, биз түйүндөрдү кезекте сактай беребиз. Кийинки деңгээлдеги түйүндөрдү сактоо үчүн, учурдагы деңгээлдеги түйүндөрдү басып өтүшүбүз керек. Ошентип, биз учурдагы деңгээлдеги түйүндөрдөн өтүп жатканда. Акыркы деңгээлди ушул деңгээлде басып чыгарабыз. Бакты оң тараптан байкаганда. Бизге көрүнүп турган жалгыз түйүн - бул деңгээлдеги эң оң түйүн. Бул ыкма орун ээлеген кезекти колдонот.

ошондой эле
Эки элементтин жыштыгынын максималдуу айырмасы, мисалы чоңураак жыштыкка ээ болгон элемент

Келгиле, чечимди рекурсияны колдонуп талкуулайлы. Чечим дарактын сол көз карашын табууга абдан окшош. Мындай ыкма менен. Биз жөн гана бактын тизилишин жасайбыз, ал тескерисинче, траверсацияга карама-каршы келет. Бирок биз ошондой эле азыркы деңгээлдеги деңгээлге жана ушул убакка чейин жеткен максималдуу деңгээлге көз салабыз. Биз сол субтриттен мурун оң субтритке өткөндө. Качан гана биз дарактын жаңы деңгээлине киребиз. Алгач эң туура түйүнгө туш болобуз. Ошентип, биз ар дайым учурдагы деңгээл максималдуу деңгээлден чоңбу же жокпу текшерип турабыз, түйүндү басып чыгарабыз. Эгерде биз компилятордун стеги үчүн талап кылынган орунду эске албасак, анда мамиле жакшыраак болот. Маселе үчүн мейкиндиктин татаалдыгы дарактын бийиктигине жараша болот, эгерде биз компилятор стеги ээлеген мейкиндикти карасак.

коду  

Эки дарактын оң көрүнүшүн басып чыгаруу үчүн 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

Комплекстик анализ  

Убакыт татаалдыгы

O (N), биз жөн гана бактын ичиндеги түйүндөрдүн үстүнөн өтүп жатабыз. Демек, даракта N түйүн бар болсо, алгоритм O (N) операцияларын аткарышы керек.

ошондой эле
Эки дарактын бирдей экендигин аныктоо үчүн код жазыңыз

Космостун татаалдыгы

O (1). Эгерде компилятор стеги колдонгон орун каралбаса, анда O (H) орун талап кылынат.