java - 需要从 inOrder 和 preOrder 返回 postOrder 树

Question

我收到了一项任务，要求我必须从二叉树的 preOder 和 inOrder 返回其 postOrder 。用纸和铅笔来做这件事很容易，但任务是开发一个自动做这件事的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));
}