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

2023-12-30 16:31:19

花无缺

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

收录于专栏 【力扣题解】



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

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

🌏题目描述

给定两个整数数组 preorderinorder ,其中 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
  • preorderinorder无重复 元素
  • 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)


🌸欢迎关注我的博客:花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏:【力扣题解】
🥇往期精彩好文:
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏? 留言📝 关注?
是我持续创作,输出优质内容的最大动力!
谢谢!

文章来源:https://blog.csdn.net/huawuque404/article/details/135306018
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。