【算法训练-二叉树 二】【重建二叉树】依据前序与中序遍历序列重建二叉树

简介: 【算法训练-二叉树 二】【重建二叉树】依据前序与中序遍历序列重建二叉树

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【重建二叉树】,使用【二叉树】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。

名曲目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍

依据前序与中序遍历序列重建二叉树【MID】

依据前序和中序的特性查找

题干

解题思路

只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位

  1. 首先通过前序遍历拿到当前树的根节点

对应题目中的结果就是:

  1. 因为中序遍历中根节点的左边是左子树,右边是右子树,所以可以依据根节点在中序遍历中的位置,知道左右子树的范围

代码实现

给出代码实现基本档案

基本数据结构二叉树

辅助数据结构哈希表

算法递归

技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    // 0 设置中序遍历 值-元素位置 的map,因为题目确保了无重复元素
    private Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();;
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // 1 条件判断
        if (preOrder == null || preOrder.length < 1 || vinOrder == null ||
                vinOrder.length < 1) {
            return null;
        }
        // 2 构建中序遍历的哈希映射
        int length = preOrder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(vinOrder[i], i);
        }
        // 递归获取左右子树
        return rebuildTree(preOrder, 0, length - 1, vinOrder, 0, length - 1);
    }
    private TreeNode rebuildTree(int[] preOrder, int preLeft, int preRight,
                                 int[] inOrder, int inLeft, int inRight) {
        // 0 设置递归终止条件
        if (preLeft > preRight) {
            return null;
        }
        // 1 首先构建根节点,也就是前序遍历的第一个元素
        TreeNode root = new TreeNode(preOrder[preLeft]);
        // 找到根节点在中序集合中的位置
        int pIndex = indexMap.get(preOrder[preLeft]);
        // 明确左子树的节点数量
        int leftSize = pIndex - inLeft;
        // 2 递归构建根节点的左子树:
        root.left = rebuildTree(preOrder, preLeft + 1, preLeft + leftSize,
                                inOrder, inLeft, pIndex - 1);
        // 3 递归构建根节点的右子树:
        root.right = rebuildTree(preOrder, preLeft + leftSize + 1, preRight,
                                 inOrder, pIndex + 1, inRight);
        return root;
    }
}

复杂度分析

时间复杂度:遍历了一遍二叉树,时间复杂度O(N);

空间复杂度:使用了辅助数据结构哈希表,空间复杂度O(N),递归栈深度极端情况下为O(N),综合来看还是O(N)

相关文章
|
5天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
9天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
27 5
|
9天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
18 2
|
12天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
22 0
|
1月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
58 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
16天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
8天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
10天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。