力扣--LCR 124. 推理二叉树

题目

某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

注意：preorder 和 inorder 中均不含重复数字。

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

代码

Map< Integer, Integer > map = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder == null || preorder.length <= 0){
        return null;
    }
    // 简历中序遍历数组的映射（就是为了快速求出某个元素的下标）
    for(int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }

    TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    return root;
}

TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
    // 前序遍历或者中序遍历为空时，表示这棵树不存在，直接返回 null
    if( l1 > r1 || l2 > r2){
        return null;
    }
    // 根节点
    TreeNode root = new TreeNode(preorder[l1]);
    // 根节点在中序遍历中的下标
    int i = map.get(preorder[l1]);
    // 递归求解
    root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i - 1);
    root.right = f(preorder, l1 + (i - l2) + 1, r1, inorder, i + 1, r2);

    return root;
}


时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 NN 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N)的栈帧空间；因此总共使用 O(N) 空间。