【力扣题解】P105-从前序与中序遍历序列构造二叉树-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P105-从前序与中序遍历序列构造二叉树-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P105-从前序与中序遍历序列构造二叉树-Java题解

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

🌏题目描述

给定两个整数数组 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 保证为二叉树的中序遍历序列

💡题解

public static TreeNode buildTree(int[] preorder, int[] inorder) {
    // 空树
    if (preorder.length == 0) {
        return null;
    }
    // 根节点
    int rootValue = preorder[0];
    // 构造树
    TreeNode root = new TreeNode(rootValue);
    // 只有一个节点, 直接返回树
    if (preorder.length == 1) {
        return root;
    }
    // 在中序数组中查找当前节点(根节点)值的索引
    int divideIndex = 0;
    for (; divideIndex < inorder.length; divideIndex++) {
        if (inorder[divideIndex] == rootValue) {
            break;
        }
    }
    // 根据当前节点的索引切割中序数组
    // 左子数组的元素就是二叉树左子树的所有节点
    // 右子数组的元素就是二叉树右子树的所有节点
    int[] leftInorder = Arrays.copyOfRange(inorder, 0, divideIndex);
    int[] rightInorder = Arrays.copyOfRange(inorder, divideIndex + 1, inorder.length);
    // 分割前序数组
    // 先移除前序数组的最后一个元素(当前节点/根节点), 因为根节点的值我们已经使用了
    preorder = Arrays.copyOfRange(preorder, 1, preorder.length);
    // 然后根据切割后的中序左右数组的长度切割后序数组
    // 因为中序数组和后序数组对应的长度都是相等的
    int[] leftPreorder = Arrays.copyOfRange(preorder, 0, divideIndex);
    int[] rightPreorder = Arrays.copyOfRange(preorder, divideIndex, preorder.length);
    // 递归构造左子节点和右子节点
    root.left = buildTree(leftPreorder, leftInorder);
    root.right = buildTree(rightPreorder, rightInorder);
    // 返回根节点
    return root;
}

时间复杂度：O(n)，二叉树有 n 个节点，需要递归 n 次递归函数。

🌏总结

由二叉树的性质我们可以知道，如果知道一个二叉树的中序与前序序列，那么我们是可以还原这棵二叉树的，那么具体怎么还原呢？二叉树的前序序列的第一个元素就是二叉树的根节点值，然后根节点值在中序序列中是在序列的中间，左右两边分别是左子树和右子树的所有节点值，所以我们使用递归，每次在前序序列中找到当前子树的根节点，使用根节点构建树，然后根据根节点将中序序列分为两个子数组，分别代表当前节点（根节点）的左右子树，而中序序列和前序序列对应的子树的序列长度是相同的，所以我们可以根据中序序列的子数组再将前序序列分为两个子数组，然后根据分开后的四个子数组递归地构建当前节点的左右子节点，就可以还原这棵二叉树。

作者：花无缺(huawuque404.com)