የተስተካከለ ቅደም ተከተል መተላለፍ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን google ጂፒ ሞርጋን የ Microsoft ሞርጋን ስታንሊ በ Uber
ዛፍ የዛፍ ተሻጋሪ

ችግሩ “ኢተራክቲካል ፕሪደር ትራቨርቫል” የሁለትዮሽ ዛፍ እንደተሰጠዎት እና አሁን ማግኘት ያስፈልግዎታል መተላለፍን ቀድመው የዛፉ ፡፡ ተደጋጋሚውን አካሄድ ሳይሆን ተጓዳኝ ዘዴን በመጠቀም የቅድመ-ትዕዛዙን መፈለጋችን ይጠየቃል።

ለምሳሌ  

የተስተካከለ ቅደም ተከተል መተላለፍጭንቅላታም መያያዣ መርፌ

 

5 7 9 6 1 4 3

ለማተም የቀረበ አቀራረብ  

የችግር መግለጫው የተሰጠውን የሁለትዮሽ ዛፍ የቅድመ-ትዕዛዞችን ቅደም ተከተሎች በመጠቀም ለማተም ይጠይቀናል። በአጠቃላይ ፣ እኛ ቀላሉን ዘዴ እንጠቀማለን ምክንያቱም ያ ቀላል ነው ፡፡ ግን አንዳንድ ጊዜ ድግግሞሽን በመጠቀም ችግሩን እንዲፈታ ይጠየቃል ፡፡ ስለሆነም እኛ የዛፉን የቅድመ-ተከተል መተላለፍን ለማከናወን እዚህ ያስፈልገናል ፡፡

ከዚህ በፊት እኛ እየተጠቀምን ነበር ተደጋጋሚነት ተሻጋሪውን ለማተም. ስለዚህ መመለሻውን ለመተካት ሀን መጠቀም አለብን ቁልል የውሂብ መዋቅር. ከዚያ በኋላ የሚፈለጉትን አንጓዎች ለማከማቸት የቁልል መረጃን መዋቅር እንጠቀማለን ፡፡ በቅድሚያ በማቋረጥ ውስጥ ፣ ሥሩን እናተምበታለን ከዚያም የግራ ንዑስ ቁጥሩን እንደገና እናተምበታለን ፣ በመጨረሻም በቀኝ ንዑስ ዛፍ እንደገና እናተም ፡፡ እዚህ በዚህ ስልተ ቀመር የአሁኑ መስቀለኛችን እስካልሆነ ድረስ የሚሮጥ ዑደት እንሰራለን ፡፡ እና ከዚያ ትክክለኛው ልጅ ካለ ትክክለኛውን ልጅ በቁልፍ ውስጥ ማከማችንን እንቀጥላለን። ከዚያ ወደ ግራ ልጅ እንሸጋገራለን ፡፡ የግራ ልጅ ዋጋ ቢስ ከሆነ አባላቱን ከመቆለፊያው ላይ አውጥተን እንደአሁኑ መስቀለኛ መንገድ እንመድባቸዋለን ፡፡ በመጨረሻ በዚህ መንገድ ዛፉን በቅደም ተከተል እናቋርጠው ነበር ፡፡

ተመልከት
የሁለትዮሽ ዛፍ ዚግዛግ ደረጃ ትዕዛዝ ተሻጋሪ

ኮድ  

የተስተካከለ የአሠራር መዘዋወርን ለማተም የ 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

ኢትሬቴሪያል ቅድመ-ቅደም ተከተልን ለማተም የጃቫ ኮድ

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ የዛፉን ንጥረ ነገሮች በሙሉ ስለ ተሻገርነው ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
ጌጣጌጦች እና ድንጋዮች Leetcode መፍትሔ

የቦታ ውስብስብነት

ኦ (ኤች) ፣ በጣም መጥፎ በሆነ ሁኔታ እያንዳንዱ አንጓዎች ትክክለኛ ልጅ ሊኖራቸው ይችላል ፡፡ ምክንያቱም ወደ ግራ ልጅ በሚወስደው መንገድ ላይ የእያንዳንዱ መስቀለኛ መንገድ ትክክለኛውን ልጅ እያከማቸነው ነው ፡፡ ስለዚህ በተደራራቢው ውስጥ በከፍተኛው ኦ (ኤች) አንጓዎች ማከማቸት እንችላለን ፡፡