Необходимо вернуть дерево postOrder из inOrder и preOrder

Question

Мне дали задание, которое говорит, что я должен вернуть postOrder бинарного дерева из его preOder и inOrder. Делать это с помощью бумаги и карандаша легко, но задача состоит в том, чтобы разработать функцию Java, которая делает это автоматически. Это должно быть сделано в Java.

Я нашел одно решение для выписки, но оно было сделано в C ++, что делает невозможным для меня перевод, я пробовал онлайн-переводчик, но он возвращает неиспользуемый код Java

 void post(char *pre,char *in,char *pos,int n)
{
  int longIzqda;

  if(n!=0){
    pos[n-1]=pre[0];
    longIzqda=strchr(in,pre[0])-in;
    post (pre+1,in,pos,longIzqda);
    post (pre+1+longIzqda,in+1+longIzqda,pos+longIzqda,n-1-longIzqda);
  }
}

package include;

import com.mtsystems.coot.NativeHelper;
import com.mtsystems.coot.String8;

public class String {
   static {
       // The online demo uses the example library "libc.so.6".
       // Have a look at the translated programs for real values.
       NativeHelper h = NativeHelper.get("libc.so.6");
       h.bindDirect(String.class);
   }

   public static native String8 strchr(String8 s, int c);
}


// ----- ----- Class 2: DemoTranslation ----- -----

package demo;

import static com.mtsystems.coot.NativeInformation.dataDistance;
import static com.mtsystems.coot.String8.nnc;
import static include.String.strchr;

import com.mtsystems.coot.String8;

public class DemoTranslation {
   public static void post(String8 pre, String8 in, String8 pos, int n) {
       int longIzqda;

       if(n != 0) {
           pos.set(n - 1, pre.get(0));
           longIzqda = (int)dataDistance(in, strchr(in, pre.get(0)));
           post(nnc(pre).shift(1), in, pos, longIzqda);
           post(nnc(pre).shift(1 + longIzqda), nnc(in).shift(1 + longIzqda), nnc(pos).shift(longIzqda), n - 1 - longIzqda);
       }
   }
}

Answer 1

Вот как можно перенести код C ++. Три дополнительных параметра используются для представления индексов в строках / символьных массивах, передаваемых в качестве первых трех аргументов.

public static void post(String pre, String in, char[] pos, int preIdx, int inIdx, int posIdx, int n) {
    if (n == 0) return;
    pos[posIdx+n-1] = pre.charAt(preIdx);
    int longIzqda = in.indexOf(pre.charAt(preIdx), inIdx) - inIdx;
    post(pre, in, pos, preIdx+1, inIdx, posIdx, longIzqda);
    post(pre, in, pos, preIdx+1+longIzqda, inIdx+1+longIzqda, posIdx+longIzqda, n-1-longIzqda);
}

public static void main(String[] args) {
    // Example use
    String pre = "5213476";
    String in = "1234567";
    int n = pre.length();
    char[] post = new char[n];
    post(pre, in, post, 0, 0, 0, n);
    System.out.println(new String(post));
}