输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Related Topics

• 树
• 数组
• 哈希表
• 分治
• 二叉树

👍 830👎 0

学二叉树入门必做题

学二叉树入门必做

关键信息

1. 前序遍历的第一个值为根节点
2. 到中序遍历中找到根节点所在位置，前面的部分为左子节点内容，后面的部分为右子节点内容
3. 得到的左右子节点的长度，重新回到前序遍历的结果中，根节点后面对应左子节点长度的部分为左子树的前序遍历，后面一部分为右子树的前序遍历
4. 拿到了步骤3和2的左子树的中序和前序遍历结果 重新做步骤1，右子树部分也同样走步骤1

前中后序遍历

左右两个子节点的顺序不变都是先左子节点，后右子节点，区别就在于根节点是先遍历，还是中间，还是最后

这分别就是前中后序遍历

相关特性

现有如图这个一对前序遍历和中序遍历结果

根据相关特效，前序遍历的第一个就是根节点，所以我们知道了，根节点为3

又中序遍历中左侧只有一个，所以左子树只有一个节点9，右子树部分暂时不知道只知道剩下部分为右侧的前序和中序遍历结果，二叉树如下

再接下来，我们把右子树部分的按照同样的逻辑处理

我们知道了右子树的根节点为20，20的左子树只有一个节点15，右子树只有一个节点7

这样我们就重新构建完成了整棵二叉树

代码

class Solution {
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int len = preorder.length-1;
        return buildTree(0,len,0,len);
    }

    public TreeNode buildTree( int preL, int preR, int inL, int inR){
        if (preL > preR){
            return null;
        }
        TreeNode node = new TreeNode(preorder[preL]);
        int len = 0;
        for (int i = inL; i <= inR; i++) {
            if (inorder[i] == preorder[preL]){
                len = i - inL;
            }
        }
        node.left = buildTree(preL+1,preL+len,inL,inL+len-1);
        node.right = buildTree(preL+len+1,preR,inL+len+1,inR);
        return node;
    }
}

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

 

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

 

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] arrL = new int[len];
        int[] arrR = new int[len];
        arrL[0] = 1;
        arrR[len-1] = 1;
        for (int i = 1; i < nums.length; i++) {
            arrL[i] = nums[i-1] * arrL[i-1];
            int rIdx = len-i-1;
            arrR[rIdx] = nums[rIdx+1] * arrR[rIdx+1];
        }

        int[] res = new int[len];
        for (int i = 0; i < res.length; i++) {
            res[i] = arrL[i] * arrR[i];
        }
        return res;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        res[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i-1] * nums[i-1];
        }
        int preR =  nums[nums.length-1];
        for (int r = nums.length-2; r >= 0; r--) {
            res[r] *= preR;
            preR *= nums[r];
        }
        return res;
    }
}