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

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

• 示例 1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

• 示例 2：

输入: preorder = [-1], inorder = [-1]
输出: [-1]

• 提示：

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

思路

要通过前序遍历（preorder）和中序遍历（inorder）构造二叉树，可以利用递归的方式来完成。前序遍历的第一个元素是根节点，通过该根节点将中序遍历划分为左子树和右子树，再递归构造子树。

1. 前序遍历的特点：

   • 第一个元素是根节点。

2. 中序遍历的特点：

   • 根节点左边的部分是左子树，右边的部分是右子树。

3. 构造过程：

   • 从前序遍历中取出根节点。
   • 在中序遍历中找到根节点的位置，划分出左子树和右子树。
   • 递归地构造左子树和右子树。

4. 以示例1为例：
   

• 时间复杂度:O(n²)
• 空间复杂度:O(n)

代码

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int n = inorder.length;
    if (n == 0) {
        return null;
    }
    int root = preorder[0];
    // 左子树的大小
    int leftSubTreeSize = 0;
    // 找到 root 在 inorder 中的下标
    for (int i = 0; i < n; i++) {
        if (root == inorder[i]) {
            leftSubTreeSize = i;
        }
    }
    // 左子树的前序遍历
    int[] leftSubTreePreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSubTreeSize);
    // 右子树的前序遍历
    int[] rightSubTreePreorder = Arrays.copyOfRange(preorder, 1 + leftSubTreeSize, n);
    // 左子树的中序遍历
    int[] leftSubTreeInorder = Arrays.copyOfRange(inorder, 0, leftSubTreeSize);
    // 右子树的中序遍历
    int[] rightSubTreeInorder = Arrays.copyOfRange(inorder, 1 + leftSubTreeSize, n);
    return new TreeNode(preorder[0], buildTree(leftSubTreePreorder, leftSubTreeInorder), buildTree(rightSubTreePreorder, rightSubTreeInorder));
}