21_从中序与后序遍历序列构造二叉树

简介: 21_从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:

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

示例 2:

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

【思路】

首先回忆一下如何根据两个顺序构造一个唯一的二叉树,就是以后续数组的最后一个元素作为切割点,先切分中序数组,根据中序数组,反过来切分后序数组。一层一层切下去,每次后序数组最后一个元素就是节点元素。

说到一层一层切割,就应该使用递归来做。

  • 第一步:如果数组大小为0的话,说明是空节点了
  • 第二步:如果不为空,那么取后续数组最后一个元素作为节点元素
  • 第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
  • 第四步:切割中序数组,切成中序左数组和中序右数组
  • 第五步:切割后序数组,切成后序左数组和后序右数组
  • 第六步:递归处理左区间和右区间
TreeNode traversal(int[] inorder, int[] postorder) {
    // 第一步
    if (postorder.size() == 0) 
        return null;
    // 第二步:后序遍历数组最后一个元素,就是当前的中间节点
    int rootValue = postorder[postorder.size() - 1];
    TreeNode root = new TreeNode(rootValue);
    
    // 叶子节点
  if (postorder.size() == 1) return root;
    
    //第三步:找到切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }
    // 第四步:切割中序数组,得到中序左数组和中序右数组
    // 第五步:切割后序数组,得到后序左数组和后序右数组
    //第六步
    root.left = traversal(中序左数组,后序左数组);
    root.right = traversal(中序右数组,后序右数组);
    return root;
}

综合版本

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    
    }
    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        // 中序遍历找到对应的根节点
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
            if(inorder[middleIndex] == rootVal)
                break;
        }
        int leftInorderStart = inorderStart; //中序左子树开始下标
        int leftInorderEnd = middleIndex; // 根节点的下标 
        int rightInorderStart = middleIndex + 1; //  中序右子树的开始下标
        int rightInorderEnd = inorderEnd;  //  中序结束的下标
        int leftPostorderStart = postorderStart;  // 后序左子树的开始下标
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);  // 后序左子树的结束下标,需要通过中序得到的middleIndex的下标来辅助计算
        int rightPostorderStart = leftPostorderEnd;  // 后序右子树的开始下标
        int rightPostorderEnd = postorderEnd - 1;  // 后序右子树的结束下标
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
        return root;
    }  
}
相关文章
|
7月前
|
域名解析 搜索推荐 网络协议
一级域名与二级域名的区别 功能及优缺点全解析
本文全面解析一级域名与二级域名的区别,详细介绍二者在所有权、管理方式、品牌价值、SEO权重等方面的差异,分析各自功能及优缺点,并给出实用的域名规划建议,同时提供专业的二级域名租用与管理解决方案,助力个人与企业合理选择域名。
7970 12
一级域名与二级域名的区别 功能及优缺点全解析
|
10月前
|
人工智能 自然语言处理 安全
2026 年适合中小企业的智能客服系统推荐,高性价比选型指南
面对数字化竞争,中小企业如何选型智能客服?本文深度解析瓴羊Quick Service、美洽、阿里云、亿捷云四大主流系统,从功能、场景、成本到安全合规全面对比。瓴羊凭借全渠道接入、AI实用化与灵活定价成高性价比首选,助力企业降本增效,实现服务智能化升级。(239字)
|
8月前
|
Linux API iOS开发
OpenClaw从搭建到精通进阶:云端/本地系统部署、免费大模型对接、Skill集成与自动化工作完整实践
OpenClaw(曾用名Clawdbot)作为一款可本地部署、支持技能扩展的自主AI智能体,已成为个人与小型团队实现信息检索、任务自动化、工作流编排的核心工具。从简单的提醒、天气查询,到实时数据抓取、定时任务、多平台消息整合,OpenClaw可通过轻量化配置实现效率翻倍。本文基于2026年最新环境,完整覆盖阿里云轻量服务器部署、macOS/Linux/Windows 11三平台本地搭建、阿里云百炼API与免费大模型对接、高频技能集成、Cron定时任务、CLI高效命令、常见问题排查,所有操作均可直接复制执行,无需额外依赖。
936 2
|
7月前
|
弹性计算 运维 安全
阿里云服务器99元1年:经济型e实例2核2G3M带宽,新老用户同享,续费价格不变
阿里云服务器99元1年,经济型e实例2核2G内存、3Mbps带宽及40G云盘的均衡配置,新老用户同享且续费不涨价,确保长期成本稳定。该服务器适用于轻量级网站、开发测试、云端学习等场景,兼具价格优势与品质保障。此外,阿里云还提供轻量应用服务器抢购、2核4G特惠云服务器等多样化选择,满足不同用户需求,助力用户以低成本实现高效云上部署。
|
8月前
|
人工智能 Rust JavaScript
1分钟吃上AI🦞小龙虾!阿里云/本地部署OpenClaw,配置免费api+集成5大热门Skills实战指南
OpenClaw的进化从未停止。当多数用户还在依赖基础对话功能时,ClawHub技能市场已诞生出一批颠覆性技能——能像人一样操作网页的Agent Browser、手机上就能合代码的GitHub技能、无需吩咐主动行动的Proactive Agent,甚至还有AI自己编写的热门技能。截至2026年3月,ClawHub前10名技能下载量均突破47万次,其中6-10名的5个技能,更是给OpenClaw装上了“眼睛(浏览器)、手脚(工具操控)和主见(主动行动)”,彻底打破“AI只能被动响应”的局限。
960 1
|
7月前
|
人工智能 安全 数据可视化
Windows 全版本 OpenClaw 搭建教程 零代码可视化一键部署
OpenClaw(小龙虾)是2026年热门开源AI自动化工具,支持Win10/11本地离线运行。零代码、全图形化、内置依赖、多模型切换、大Token额度,5–10分钟一键部署。数据不出设备,安全可控,适配办公全场景。(239字)
623 1
|
11月前
|
安全 Java API
添加 Swagger2 的 Maven 依赖
本文介绍如何在Spring Boot项目中集成Swagger2(2.2.2版本),通过添加Maven依赖、配置SwaggerConfig类,实现在线API文档生成功能,并提供访问路径与生产环境安全禁用建议。
|
11月前
|
传感器 人工智能 安全
【口碑排行】 甲方真实的投票:售后服务场景下,客户满意度最高的语音机器人品牌盘点
在2025大模型落地元年,语音机器人成为售后数字化转型关键。本文基于IDC、信通院等权威数据,从交互自然度、业务闭环、工程化交付三大维度,盘点主流服务品牌,助力企业选型实现降本增效与95%以上客户满意度双目标。
|
Android开发 iOS开发 容器
HarmonyOS实战:快速实现一个上下滚动的广告控件
本文介绍了如何在鸿蒙系统中实现一个支持上下滚动的广告控件。功能包括自动滚动、手动滑动、广告删除、自定义播放间隔等。通过使用 Swiper 组件和相关属性(如 disableSwipe、autoPlay),结合数据源操作与手势支持,可轻松完成开发。相比 Android 和 iOS,鸿蒙实现方式更简洁,满足日常需求。建议点赞收藏并动手实践!
408 0
HarmonyOS实战:快速实现一个上下滚动的广告控件
|
人工智能 自然语言处理 算法
MT-MegatronLM:国产训练框架逆袭!三合一并行+FP8黑科技,大模型训练效率暴涨200%
MT-MegatronLM 是摩尔线程推出的面向全功能 GPU 的开源混合并行训练框架,支持多种模型架构和高效混合并行训练,显著提升 GPU 集群的算力利用率。
1353 18