当前位置: 首页 > news >正文

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

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

解题思路:
前序遍历序列的第一个元素就是根节点,然后在中序遍历序列中找到根节点的位置,它的前面就是左子树的中序遍历,后面部分就是右子树的中序遍历。
根据左子树的大小可以将前序遍历分为左子树的前序遍历和右子树的前序遍历。
这样我们就分别得到了左子树和右子树的前序遍历和中序遍历。这是和原问题一样的子问题,可以用递归问题解决。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;if(n == 0){return null;}TreeNode root = new TreeNode(preorder[0]);int rootIdx = indexOfRoot(inorder, preorder[0]);root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIdx), Arrays.copyOfRange(inorder, 0, rootIdx));root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIdx, n), Arrays.copyOfRange(inorder, 1 + rootIdx, n));return root;}private int indexOfRoot(int[] a, int target){for(int i = 0; ; i++){if(a[i] == target){return i;}}}
}
http://www.lqws.cn/news/477217.html

相关文章:

  • DRTM动态度量信任根的POC概念验证
  • 优化通义大模型推理性能:企业级场景下的延迟与成本削减策略
  • YSYX学习记录(十一)
  • DAY 39 图像数据与显存
  • ProtoBuf:通讯录4.0实现 序列化能⼒对⽐验证
  • Rust 引用与借用
  • 47.第二阶段x64游戏实战-封包-分析打怪call
  • winform mvvm
  • 关于存储与网络基础的详细讲解(从属GESP二级内容)
  • 【机器学习四大核心任务类型详解】分类、回归、聚类、降维都是什么?
  • 人工智能、机器人最容易取哪些体力劳动和脑力劳动
  • AWS 使用图形化界面创建 EKS 集群(零基础教程)
  • Spring AI 项目实战(十):Spring Boot + AI + DeepSeek 构建智能合同分析技术实践(附完整源码)
  • java中HashMap和ConcurrentHashMap的共性以及区别
  • 《高等数学》(同济大学·第7版)第五章 定积分 第四节反常积分
  • 用可观测工具高效定位和查找设计中深度隐藏的bug
  • 网络安全智能体:重塑重大赛事安全保障新范式
  • 啥是 SaaS
  • [xiaozhi-esp32] 构建智能AI设备 | 开发板抽象层 | 通信协议层
  • 【ELK(Elasticsearch+Logstash+Kibana) 从零搭建实战记录:日志采集与可视化】
  • Elasticsearch Kibana (一)
  • spring碎片
  • 针对数据仓库方向的大数据算法工程师面试经验总结
  • 点点(小红书AI搜索):生活场景的智能搜索助手
  • Typecho博客3D彩色标签云插件(Handsome主题优化版)
  • 2.jupyter切换使用conda虚拟环境的最佳方法
  • 【DataWhale组队学习】AI办公实践与应用
  • Mysql—锁相关面试题(全局锁,表级锁,行级锁)
  • SpringCloudGateway(spel)漏洞复现 Spring + Swagger 接口泄露问题
  • 大零售生态下开源链动2+1模式、AI智能名片与S2B2C商城小程序的协同创新研究