געפֿינען פּאָסטאָרדער טראַווערסאַל פון BST פֿון פּריאָרדער טראַווערסאַל


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן פאָורקיטעס PayU
ביינערי זוכן בוים בוים טראַווערסאַל

פּראָבלעם סטאַטעמענט

די פּראָבלעם "געפֿינען פּאָסטאָרדער טראַווערסאַל פון BST פֿון פּרעאָרדער טראַווערסאַל" שטאַטן אַז איר וועט געבן אַ פאַראָרדערונג דורך אַ ביינערי זוכן בוים. געפֿינען די פּאָסטאָרדער טראַווערסאַל מיט די געגעבן ינפּוט.

בייַשפּיל

געפֿינען פּאָסטאָרדער טראַווערסאַל פון BST פֿון פּריאָרדער טראַווערסאַל

preorder traversal sequence: 5 2 1 3 4 7 6 8 9
1 4 3 2 6 9 8 7 5

צוגאַנג

דער געגעבן פּראָבלעם זאגט אַז מיר זענען צוגעשטעלט מיט אַ פּרעאָרדער דורך סיקוואַנס פון אַ ביינערי זוכן בוים. איצט מיר דאַרפֿן צו געפֿינען די פּאָסטאָרדער טראַווערסאַל פון דעם בוים, וואָס האט די זעלבע פּרעאָרדער טראַווערסאַל ווי אַרייַנשרייַב. מיר דאַרפֿן צו סאָלווע דעם פּראָבלעם יפישאַנטלי.

א נאַיוו צוגאַנג איז צו ערשטער נוצן די פּרעאָרדער דורכפאָר און בויען די BST. דערנאָך טאָן אַ פּאָסטאָרדער דורך דעם נייַ קאַנסטראַקטאַד בוים. אָבער, דעם צוגאַנג איז באַטלאָניש וועגן פּלאַץ. ווייַל די קאַנסטראַקטאַד בוים איז אַקטינג ווי אַ אָוווערכעד.

צו סאָלווע די פּראָבלעם יפישאַנטלי, מיר גיין דורך די ינפּוט מענגע. די ינפּוט מענגע איז אונדזער פּרעאָרדער טראַווערסאַל. אַזוי מיר גיין דורך די פּרעאָרדער טראַווערסאַל און געפֿינען צי די קראַנט עלעמענט זאָל ליגן. ווען מיר אָנהייבן מיט דער ערשטער עלעמענט, מיר שטעלן אַ קייט פון מינימום ינטאַדזשער ווערט צו מאַקסימום ינטעגער ווערט. ווייַל די פּרעאָרדער טראַווערסאַל האט דער וואָרצל איידער די לינקס און רעכט סאַבסטרי. מיר וויסן אַז אויב די לינקס סובטרעע יגזיסץ, די עלעמענטן זאָל זיין פֿון אַ מינימום ינטאַדזשער ווערט צו אַ ווערט ווייניקער ווי דער וואָרצל. סימילאַרלי פֿאַר די רעכט סובטרעע, וואָס זאָל זיין פֿון די גרעסערע שורש ווערט צו אַ מאַקסימום גאַנץ נומער. איצט אויב דער קראַנט עלעמענט איז ניט אין דעם קייט. דערנאָך דאָס זאָל ליגן אין די אנדערע סובטרעע (דאָס איז אויב עס איז נישט אין די קייט פֿאַר לינקס סובטרעע ווי עס זאָל ליגן אין די רעכט סובטרעע און וויצע ווערסאַ).

קאָדעקס

C ++ קאָד צו געפֿינען פּאָסטאָרדער טראַווערסאַל פון BST פֿון פּריאָרדער טראַווערסאַל

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

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
  // base case
  if (idx == n)
    return;
  // if current element does not belong to current subtree
  if (input[idx] < mn || input[idx] > mx) {
    return;
  }

  // store the value of root ro print after printing its subtrees
  int root = input[idx];
  idx++;

  // recursively solve for left and right subtree
  preToPost(input, n, mn, root, idx);
  preToPost(input, n, root, mx, idx);
  // print root
  cout<<root<<" ";
}

int main()
{
  int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
  int n = (sizeof input)/(sizeof input[0]);
  int idx = 0;
  	preToPost(input, n, INT_MIN, INT_MAX, idx);
}
1 4 3 2 6 9 8 7 5

Java קאָד צו געפֿינען פּאָסטאָרדער דורך BST פֿון פּריאָרדער טראַווערסאַל

import java.util.*;

class Main{
  static int idx = 0;
  static void preToPost(int input[], int n, int mn, int mx)
  {
    // base case
    if (idx == n)
      return;
    // if current element does not belong to current subtree
    if (input[idx] < mn || input[idx] > mx) {
      return;
    }

    // store the value of root ro print after printing its subtrees
    int root = input[idx];
    idx++;

    // recursively solve for left and right subtree
    preToPost(input, n, mn, root);
    preToPost(input, n, root, mx);
    // print root
    System.out.print(root+" ");
  }

  public static void main(String[] args)
  {
    int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
    int n = input.length;
    	preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
}
1 4 3 2 6 9 8 7 5

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N)ווייַל מיר מוזן דורכגיין די גאנצע מענגע.

ספעיס קאַמפּלעקסיטי

אָ (N)ווייַל פון די קאַמפּיילער סטאַק וואָס איז געניצט פֿאַר די רעקורסיווע פאַנגקשאַנז.