data-structures - 如何从 Preorder 和 Inorder Traversal 中找到水平顺序遍历

Question

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

标签： data-structurestree

Answer 1

这是我的解决方案：

1. 从 Inorder 和 PreOrder 遍历构建树。

2. 遍历树并找到级别顺序遍历。

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;
    }
}