题目：从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

例如给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \ 
  9   20
     /  \ 
    15   7

解题思路

1. 先序遍历为：根节点，左子树，右子树
2. 中序遍历为：左子树，根节点，右子树
3. 根据先序遍历中的根节点的值找到中序遍历中根节点位置，从而定位左子树和右子树的长度。
4. 递归实现树的建立
5. 哈希表存储中序遍历中索引与值的映射关系，以便在O(1)的时间内在中序遍历中查找到根节点位置。

代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map map = new HashMap();
    int[] preOrder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preOrder = preorder;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i],i);
        }
        return helper(0, preorder.length, 0, inorder.length);
    }
    private TreeNode helper(int pStart, int pEnd ,int inStart, int inEnd){
        if(pStart == pEnd) return null;
        TreeNode root = new TreeNode(preOrder[pStart]);
        int index = map.get(preOrder[pStart]);
        int num = index-inStart;
        root.left = helper(pStart+1, pStart+num+1, inStart, inStart+num);
        root.right = helper(pStart+num+1, pEnd, inStart+num+1, inEnd); 
        return root;
    }
}

复杂度分析

1.时间复杂度: O(N) 只需要遍历数组一遍
2.空间复杂度: O(N) 建立哈希表所花费的空间开销