按层打印二叉树

2018-05-28

时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一棵二叉树的前序（根、左、右）和中序（左、根、右）的打印结果，输出此二叉树按层（从左往右）打印结果。
例如一棵二叉树前序：1 2 4 5 3；中序：4 2 5 1 3。可以构建出下图所示二叉树：

按层打印的结果则为：1 2 3 4 5。

输入
第一行只有一个数字，表示二叉树的节点数n（1<=n<=1000）;
第二行由a1,a2,…,an(1<=ai<=1000)组成的整数序列（用空格分隔）—表示前序打印结果；
第三行由b1,b2,…,bn(1<=bi<=1000)组成的整数序列（用空格分隔）—表示中序打印结果。

输出
c1,c2,…,cn，用空格分隔—表示按层打印的结果。

样例输入
5
1 2 4 5 3
4 2 5 1 3

样例输出
1 2 3 4 5

下面是我的答案，如果你的更好的解决方案，请在下方评论，大家一起交流学习！

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int nodes = Integer.parseInt(scanner.nextLine());
        String previous = scanner.nextLine();
        String middle = scanner.nextLine();
        int[] pre = new int[nodes];
        int[] mid = new int[nodes];
        for (int i = 0; i < nodes; i++) {
            pre[i] = Integer.parseInt(previous.split(" ")[i]);
            mid[i] = Integer.parseInt(middle.split(" ")[i]);
        }
        Node node = binaryTree(pre, mid);
        // System.out.print(node.value + " ");
        ArrayList nodeList = new ArrayList();
        nodeList.add(node);
        output(nodeList);

    }

    public static void output(ArrayList node) {
        if (node != null && node.size() > 0) {
            ArrayList nodeList = new ArrayList();
            for (Node n : node) {
                if (n != null) {
                    System.out.print(n.value + " ");
                    nodeList.add(n.left);
                    nodeList.add(n.right);
                }
            }
            output(nodeList);
        }
    }

    public static Node binaryTree(int[] pre, int[] mid) {
        if (pre == null || mid == null) {
            return null;
        }
        Node mm = constructBinaryTreeCore(pre, mid, 0, pre.length - 1, 0, mid.length - 1);
        return mm;
    }

    public static Node constructBinaryTreeCore(int[] pre, int[] mid, int preStart, int preEnd, int midStart,
            int midEnd) {
        Node tree = new Node(pre[preStart]);
        tree.left = null;
        tree.right = null;
        if (preStart == preEnd && midStart == midEnd) {
            return tree;
        }
        int root = 0;
        for (root = midStart; root < midEnd; root++) { if (pre[preStart] == mid[root]) { break; } } int leifLength = root - midStart; int rightLength = midEnd - root; if (leifLength > 0) {
            tree.left = constructBinaryTreeCore(pre, mid, preStart + 1, preStart + leifLength, midStart, root - 1);
        }
        if (rightLength > 0) {
            tree.right = constructBinaryTreeCore(pre, mid, preStart + 1 + leifLength, preEnd, root + 1, midEnd);
        }
        return tree;
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int k) {
        value = k;
    }
}