如何从预序和中序遍历中查找级别顺序遍历

Question

二叉树的预序遍历是{8,5,9,7,1,12,4,11,3}，其顺序是{9,5,1,7,12,8,4,3,11}。用它构造二叉树并执行级别顺序遍历。最后构造一个二叉搜索树（BST），从左到右依次获取在上述级别顺序遍历中出现的键值。这个BST的级别顺序遍历是什么？

Answer 1

这是我的解决方案：

>

从索引和预排序遍历构建树。

遍历树并查找级别顺序遍历。

public class PreAndInOrderToLevelOrderTraversal {
    static class Node {
        int val;
        Node left;
        Node right;
        public Node(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    static int[] pre;
    static int[] in;
    static ConcurrentHashMap<Integer, Integer> map;
    static Node treeRoot;
    static int preIndex = 0;

    public static void main(String[] args) {
        map = new ConcurrentHashMap<>();
        pre = new int[]{1, 2, 4, 5, 3};
        in = new int[]{4, 2, 5, 1, 3};

        treeRoot = buildTreeFromPreorderAndInOrder(pre, in, map);
        System.out.println(treeRoot.val);
        printLevelOrder();
    }

    public static void printLevelOrder() {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(treeRoot);
        while (!queue.isEmpty()) {

            /* poll() removes the present head.
            For more information on poll() visit
            http://www.tutorialspoint.com/java/util/linkedlist_poll.htm */
            Node tempNode = queue.poll();
            System.out.print(tempNode.val + " ");

            /*Enqueue left child */
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }

            /*Enqueue right child */
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }

    }

    private static Node buildTreeFromPreorderAndInOrder(int[] pre, int[] in, ConcurrentHashMap<Integer, Integer> map) {
        // location of the item in the inorder traversal to find it quick in O(1)
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return helper(in, pre, 0, pre.length - 1, map);
    }

    private static Node helper(int[] in, int[] pre, int inStart, int inEnd, ConcurrentHashMap<Integer, Integer> map) {
        if (inStart > inEnd) return null;
        int curr = pre[preIndex++];
        Node tNode = new Node(curr);
        if (inStart == inEnd) return tNode;
        int inIndex = map.get(curr);
        tNode.left = helper(in, pre, inStart, inIndex - 1, map);
        tNode.right = helper(in, pre, inIndex + 1, inEnd, map);
        return tNode;
    }
}