已知如下一棵二叉树对应的字符序列（层次遍历序列）为：ABC##EF#G####，其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列，请使用二叉链表构造该二叉树，并输出该二叉树的中序遍历。

已知如下一棵二叉树对应的字符序列（层次遍历序列）为：ABC##EF#G####，其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列，请使用二叉链表构造该二叉树，并输出该二叉树的中序遍历。

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        String s = "ABC##EF#G####";
        TreeNode root = buildTree(s);
        inorderTraversal(root);
    }

    public static TreeNode buildTree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(s.charAt(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (i < s.length() && s.charAt(i) != '#') {
                node.left = new TreeNode(s.charAt(i));
                queue.offer(node.left);
            }
            i++;
            if (i < s.length() && s.charAt(i) != '#') {
                node.right = new TreeNode(s.charAt(i));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }

    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
}