BOJ. Iterate Tree (2263)

Problem link

Inorder traversal places a node between its left and right subtrees, while postorder traversal ends each subtree with its root. For a current pair of ranges, the last postorder value is therefore the subtree root. A value-to-inorder-index table finds the split in constant time: the number of values to the left of that index determines the left subtree’s postorder range; the remaining preceding values belong to the right subtree.

Process these ranges with an explicit stack rather than recursive calls. Each frame stores inclusive inorder and postorder bounds. Emit its root when removing the frame, then push the right frame followed by the left frame so the left subtree is processed next and output is preorder. Every node is indexed and processed once, so time and auxiliary space are both O(N). The explicit stack uses O(N) space in the worst case and avoids overflowing the call stack on a skewed tree.

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);
  }
}