题解 | #二叉树遍历#

根据先序遍历字符串构建二叉树：

1. 遍历字符串，使用递归的方式构建二叉树，每次取出字符串中的一个字符，如果是#表示空树，则返回null，否则创建一个新的节点，并递归构建其左子树和右子树。
2. 中序遍历顺序：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。 使用递归的方式进行中序遍历，先遍历左子树，然后将当前节点的值添加到结果字符串中，最后遍历右子树。

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

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

    public static int index = 0; //作为字符串遍历时的下标
    public static TreeNode createTree(String str){
         TreeNode root = null;
         if(str.charAt(index) != '#'){
         //创建一个新节点
            root = new TreeNode(str.charAt(index));
            index++;
            //构建左子树
            root.left = createTree(str);
            //构建右子树
            root.right = createTree(str);
         }else{
            index++;
         }
         //当字符是#表示空树，返回null，不是#时会创建一个新的节点，返回的是该节点
         return root;
    }


    public static void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        //先遍历左子树
        inOrder(root.left);
        //将当前节点的值添加到结果字符串中
        System.out.print(root.val+" ");
        //最后遍历右子树
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();//读取先序遍历字符串
        
        TreeNode root = createTree(str);//构建二叉树
        inOrder(root);//中序遍历
    }
}

我们并不用考虑，index 是否会越界的情况，因为我们根本没有用 index 来控制循环次数，而是一边前序遍历，一边构建整棵树。