Давтан урьдчилсан захиалга  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Google-ийн JP Morgan Microsoft- Morgan Stanley Uber
Мод Мод хөндлөн гарах

"Давталттай урьдчилан захиалагчийн дамжуулалт" гэсэн асуудалд танд хоёртын мод өгч байгаа тул одоо үүнийг олох хэрэгтэй гэж заасан байдаг урьдчилсан захиалга модны. Бидэнд рекурсив аргыг биш харин давталтын аргыг ашиглан урьдчилсан захиалгыг олох шаардлагатай байна.

Жишээ нь  

Давтан урьдчилсан захиалгаPin

 

5 7 9 6 1 4 3

Хэвлэх арга  

Асуудлын шийдэл нь өгөгдсөн хоёртын модны урьдчилсан захиалгыг давталтын аргаар хэвлэхийг биднээс хүсдэг. Ерөнхийдөө бид илүү хялбар тул рекурсив аргыг ашигладаг. Гэхдээ заримдаа давталтыг ашиглан асуудлыг шийдэхийг хүсдэг. Тиймээс бид энд модны давталтын урьдчилсан дарааллыг хийх шаардлагатай байна.

Өмнө нь бид ашиглаж байсан давтлага хөндлөвчийг хэвлэх. Тиймээс рекурсыг орлуулахын тулд бид a-г ашиглах ёстой стек мэдээллийн бүтэц. Тиймээс бид дараа нь шаардлагатай цэгүүдийг хадгалахын тулд стек өгөгдлийн бүтцийг ашиглах болно. Урьдчилан захиалахдаа эхлээд root-г хэвлээд дараа нь зүүн дэд модыг рекурсив хэлбэрээр, эцэст нь баруун дэд модыг рекурсив байдлаар хэвлэнэ. Энэ алгоритм дээр бид одоогийн зангилаа хоосон биш болтол ажиллах циклийг ажиллуулах болно. Дараа нь бид зөв хүүхэд байгаа бол зөв хүүхдийг овоолох болно. Дараа нь бид зүүн хүүхэд рүү шилждэг. Хэрэв зүүн хүүхэд хоосон байвал бид элементүүдийг стекээс устгаж тэдгээрийг одоогийн зангилаа болгоно. Ингэж эцэст нь бид модыг урьдчилж захиалгаар туулах байсан.

мөн үзнэ үү
Хоёртын модны зигзаг түвшний захиалга Traversal

код  

Давтан урьдчилсан захиалгын дамжуулалтыг хэвлэх 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 preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

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

  preorder(root);
}
5 7 9 6 1 4 3

Давтамжтай урьдчилсан захиалгын дамжуулалтыг хэвлэх Java код

import java.util.*;

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

class Main{

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

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид модны бүх элементүүдийг туулсан. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

мөн үзнэ үү
Jewels and Stones Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал

O (H), хамгийн муу тохиолдолд зангилаа тус бүр нь зөв хүүхэдтэй болж чаддаг. Учир нь бид зангилаа бүрийн зөв хүүхдийг зүүн хүүхдийн замд хадгалж байгаа юм. Тиймээс бид стек дэх хамгийн их O (H) цэг дээр хадгалах боломжтой.