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

题目

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

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

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

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

方法（递归）

二叉树的三种遍历次序依次为：

• 前序遍历：根、左、右
• 中序遍历：左、根、右
• 后序遍历：左、右、根

一个二叉树的前序、中序、后序遍历序列可以看作由如下部分构成：

• 前序遍历序列：

    [根节点, [左子树的前序遍历], [右子树的前序遍历]]
  

• 中序遍历序列：

    [[左子树的中序遍历], 根节点, [右子树的中序遍历]]
  

• 后序遍历序列：

    [[左子树的后序遍历], [右子树的后序遍历], 根节点]
  

因此，我们由前序遍历和中序遍历构造二叉树的步骤为：

1. 在前序遍历序列中得到根节点
2. 在中序遍历序列中找到根节点的位置，其左边为左子树中序遍历序列，右边为右子树中序遍历序列。
3. 在前序遍历序列中也找到左右子树对应的前序遍历序列（根据一棵树的中序遍历序列和前序遍历序列的长度相同）
4. 递归生成左右子树
5. 将根节点与左右子树连接

为了降低空间复杂度，我们不对原树的preorder和inorder切分生成新的数组序列，而是采用双指针记下子树的序列在preorder和inorder的索引范围

代码

class Solution {
    private int[] preorder;
    private int[] inorder;
    HashMap<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        //用一个哈希表将中序遍历序列的每个元素和其下标对应起来，方便之后在inorder中查找根节点位置索引
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return helper(0, preorder.length,0, inorder.length);
    }

    //由前序遍历序列和中序遍历序列构造二叉树
    //前序遍历序列由preorder中索引pre_start和pre_end间的元素构成
    //中序遍历序列由inorder中索引in_start和in_end间的元素构成
    private TreeNode helper(int pre_start, int pre_end, int in_start, int in_end) {
        //递归结束条件：前序或中序遍历序列为空
        if(pre_start == pre_end || in_start == in_end)
            return null;
        int root_val = preorder[pre_start];
        TreeNode root = new TreeNode(root_val);
        int root_index = map.get(root_val);
        //左子树的前序遍历序列和中序遍历的长度
        int left_num = root_index - in_start;
        TreeNode L = helper(pre_start + 1, pre_start + 1 + left_num, in_start, root_index);
        TreeNode R = helper(pre_start + 1 + left_num, pre_end, root_index + 1, in_end);
        root.left = L;
        root.right = R;
        return root;
    }
}

• 时间复杂度：O(n), n为树中节点的个数
• 空间复杂度：O(n), 需要用O(n)存储哈希表，O(h)存储递归时的栈空间（h为树高度 h < n）,因此空间复杂度为O(n)