import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

class Main {

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.solve();

    }

    public void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            // Node root = build(br.readLine(););
            // printByLevel(root);
            printByLevel(build(br.readLine()));
            // printByPostorder(root);
            // System.out.println();
        }
    }

    public Node build(String s) {
        Node node = new Node(s.charAt(s.length() - 1));

        if (s.length() <= 1) {
            return node;
        }
        if (s.length() == 3) {
            node.left = new Node(s.charAt(0));
            node.right = new Node(s.charAt(1));
            return node;
        }

        int i;
        int count = 2;
        for (i = 2; i < s.length() - 1; i++) {
            if (s.charAt(i) <= 'Z') {
                count -= 2;
                // if left child is a subtree;
                if (count == 0) {
                    // System.out.print(s.substring(0, i + 1) + ", "
                    // + s.substring(i + 1, s.length() - 1));
                    // System.out.println();
                    node.left = build(s.substring(0, i + 1));
                    node.right = build(s.substring(i + 1, s.length() - 1));
                    break;
                }
                count++;
            }
            else
                count++;

        }
        // if the left child is just a number.
        if (count == 2) {
            node.left = build("" + s.charAt(0));
            node.right = build(s.substring(1, s.length() - 1));
        }
        return node;
    }

    public void printByPostorder(Node root) {
        if (root == null) {
            return;
        }
        printByPostorder(root.left);
        printByPostorder(root.right);
        System.out.print(root.data);
    }

    public void printByLevel(Node root) {
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(root);
        for (int i = 0; i < q.size(); i++) {
            Node tmp = q.get(i);
            if (tmp.left != null) {
                q.add(tmp.left);
                q.add(tmp.right);
            }
        }
        for (int i = q.size() - 1; i >= 0; i--)
            System.out.print(q.get(i).data);
        System.out.println();
    }
}

class Node {
    public char data;
    public Node left;
    public Node right;

    public Node(char c) {
        this.data = c;
        this.left = null;
        this.right = null;
    }
}

• Re:WA了很久, 还请牛人给点测试数据:(Java) (3052) Zechel 2021-11-16 15:40:12