105. 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

描述

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

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

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
3
/ \
9 20
/ \
15 7

题解

先序遍历的顺序是 Root -> Left -> Right，这就能方便的从根开始构造一棵树。
首先，preorder中的第一个元素一定是树的根，这个根又将inorder序列分成了左右两棵子树。现在我们只需要将先序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。

class Solution {
    int preIdx = 0;
    int[] preorder;
    int[] inorder;
    Map<Integer, Integer> idxMap = new HashMap<>();
    public TreeNode helper(int inLeft, int inRight) {
        // if there is no element to construct subtrees
        if (inLeft == inRight) {
            return null;
        }
        // pick up preIdx element as a root
        int rootVal = preorder[preIdx];
        TreeNode root = new TreeNode(rootVal);
        // root splits inorder list into left and right subtrees
        int index = idxMap.get(rootVal);
        //recursion
        preIdx++;
        // build left subtree
        root.left = helper(inLeft, index);
        // build right subtree
        root.right = helper(index + 1, inRight);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        // build a hashMap value -> its index
        int idx = 0;
        for (Integer val : inorder) {
            idxMap.put(val, idx++);
        }
        return helper(0, inorder.length);
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：，存储整棵树的开销。