1.要点

• 二叉树遍历
• 重复在数组中查找某个数时（重复+查找=二重循环），应考虑是否可以用map

2.题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

3.示例

给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

4.限制：

0 <= 节点个数 <= 5000

5.代码

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return preorder.length == 0 ? null : buildNode(preorder, inorder);
    }

    public TreeNode buildNode(int[] preorder, int[] inorder) {
        int rootNodeIndex = -1;
        int rootNodeValue = 0;
        Map<Integer,Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }

        for (int i = 0; i < preorder.length; i++) {
                if (null != inorderMap.get(preorder[i])) {
                    rootNodeIndex = inorderMap.get(preorder[i]);
                    rootNodeValue = preorder[i];
                    break;
                }
        }

        TreeNode treeNode = new TreeNode(rootNodeValue);
        treeNode.left = rootNodeIndex > 0 ?
                buildNode(preorder, Arrays.copyOfRange(inorder, 0, rootNodeIndex)) :
                null;
        treeNode.right = rootNodeIndex < inorder.length - 1 ?
                buildNode(preorder, Arrays.copyOfRange(inorder, rootNodeIndex + 1, inorder.length)) :
                null;
        return treeNode;
    }