中間順ではノードが左・右の部分木の間に置かれ、後行順では各部分木の最後の値がその根になります。そのため、現在処理している 2 つの範囲では、後行順の最後の値が部分木の根です。値から中間順のインデックスを引く表を使えば、分割位置を定数時間で見つけられます。その位置より左にあるノード数で左部分木の大きさが決まり、残りの先頭側の後行順範囲が右部分木に対応します。
再帰呼び出しの代わりに、範囲を明示的なスタックで処理します。各フレームには中間順・後行順それぞれの両端インデックスを格納します。フレームを取り出したときに根を出力し、右の範囲を先に積んでから左の範囲を積むと、左部分木が先に処理され、先行順になります。各ノードのインデックス登録と処理は 1 回ずつなので、時間計算量と補助空間計算量はいずれも O(N) です。最悪時、明示的なスタックは O(N) の空間を使いますが、偏った木でも呼び出しスタックがあふれません。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine().trim());
int[] inorder = new int[n];
int[] postorder = new int[n];
int[] inorderIndex = new int[n + 1];
StringTokenizer values = new StringTokenizer(input.readLine());
for (int i = 0; i < n; i++) {
inorder[i] = Integer.parseInt(values.nextToken());
inorderIndex[inorder[i]] = i;
}
values = new StringTokenizer(input.readLine());
for (int i = 0; i < n; i++) {
postorder[i] = Integer.parseInt(values.nextToken());
}
int[] inLeftStack = new int[n];
int[] inRightStack = new int[n];
int[] postLeftStack = new int[n];
int[] postRightStack = new int[n];
int top = 0;
inLeftStack[top] = 0;
inRightStack[top] = n - 1;
postLeftStack[top] = 0;
postRightStack[top] = n - 1;
StringBuilder preorder = new StringBuilder();
while (top >= 0) {
int inLeft = inLeftStack[top];
int inRight = inRightStack[top];
int postLeft = postLeftStack[top];
int postRight = postRightStack[top--];
int root = postorder[postRight];
preorder.append(root).append(' ');
int rootIndex = inorderIndex[root];
int leftSize = rootIndex - inLeft;
if (rootIndex < inRight) {
top++;
inLeftStack[top] = rootIndex + 1;
inRightStack[top] = inRight;
postLeftStack[top] = postLeft + leftSize;
postRightStack[top] = postRight - 1;
}
if (inLeft < rootIndex) {
top++;
inLeftStack[top] = inLeft;
inRightStack[top] = rootIndex - 1;
postLeftStack[top] = postLeft;
postRightStack[top] = postLeft + leftSize - 1;
}
}
System.out.println(preorder);
}
}