105. 从前序与中序遍历序列构造二叉树

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

注意:
你可以假设树中没有重复的元素。

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题思路

基于前序遍历和中序遍历的特点, 分别找到子树的范围, 然后递归处理。

前缀遍历的第一个节点就是根节点。
依据此根节点找到中序遍历此节点的位置.中序遍历此位置左边是其左子树, 右边是其右子树。
依据左子树和右子树的节点的数量, 可以在前序遍历数组找到其左子树和右子树的前序遍历序列。

递归此过程即可。

由于需要遍历中序序列找根节点, 时间复杂度较高。所以可以使用一个HashMap存储每个节点的位置。

private final Map<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                          int[] inorder, int inStart, int inEnd) {

    if (inStart > inEnd) {
        return null;
    }
    int rootValue = preorder[preStart];
    int rootIndex = map.get(rootValue);
    TreeNode rootNode = new TreeNode(rootValue);
    // 将中序数组分为左右子树

    rootNode.left = buildTree(preorder, preStart + 1, preStart + (rootIndex - inStart),
            inorder, inStart, rootIndex - 1);

    rootNode.right = buildTree(preorder, preStart + (rootIndex - inStart) + 1, preEnd,
            inorder, rootIndex + 1, inEnd);

    return rootNode;
}