[PAT-A] 1086 Tree Traversals Again

Java

package PAT_A1086_Tree_Traversals_Again;

import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

public class Main {
    static final int N = 40;
    static int n;
    static int root;
    static int[] l = new int[N];
    static int[] r = new int[N];
    static Vector<Integer> postorder = new Vector<>();

    static void dfs(int u) {
        if (u == 0) return;

        dfs(l[u]);
        dfs(r[u]);
        postorder.add(u);
    }

    static void print() {
        for (int i = 0; i < postorder.size(); ++i) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(postorder.get(i));
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        Stack<Integer> stk = new Stack<>();
        int lastNode = 0;
        String lastOp = "";
        for (int i = 0; i < 2 * n; ++i) {
            String op = scanner.next();
            if ("Push".equals(op)) {
                int node = scanner.nextInt();
                if (lastNode == 0) {
                    root = node;
                } else {
                    if ("Push".equals(lastOp)) {
                        l[lastNode] = node;
                    } else {
                        r[lastNode] = node;
                    }
                }
                lastNode = node;
                stk.push(node);
            } else {
                int node = stk.peek();
                stk.pop();
                lastNode = node;
            }
            lastOp = op;
        }

        dfs(root);
        print();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 40;

int n;
int root, l[N], r[N];
vector<int> postorder;

void dfs(int u) {
    if (!u) return;

    dfs(l[u]);
    dfs(r[u]);
    postorder.push_back(u);
}

void print() {
    for (int i = 0; i < postorder.size(); ++i) {
        if (i > 0) printf(" ");
        cout << postorder[i];
    }
}

int main() {
    cin >> n;

    stack<int> stk;
    int last_node = 0;
    string last_op;
    for (int i = 0; i < 2 * n; ++i) {
        string op;
        cin >> op;

        if (op == "Push") {
            int node;
            cin >> node;

            if (!last_node) {
                root = node;
            } else {
                if (last_op == "Push") l[last_node] = node;
                else r[last_node] = node;
            }

            last_node = node;
            stk.push(node);
        } else {
            int node = stk.top();
            stk.pop();
            last_node = node;
        }
        last_op = op;
    }

    dfs(root);
    print();
}