代码随想录:从中后/中前遍历序列构造二叉树

devtools/2025/1/3 7:29:10/

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

用分治思想,后序遍历是左右中,中序遍历是左中右,后序遍历的最后一个元素就是根节点,

在中序遍历中找到它的位置,它前面的为左子树,后面的为右子树,并能计算左右子树结点个数,算下标差即可,然后递归算每一棵子树,当成一棵树来处理,中序遍历对应前几个结点与后序遍历前几个结点为一棵树上的结点。

java">/*** 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 {HashMap<Integer,Integer> m=new HashMap<>();int[] post;public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i=0;i<inorder.length;i++)
{m.put(inorder[i],i);
}post=postorder;return tree(0,inorder.length-1,0,postorder.length-1);}TreeNode tree (int inbegin,int inend,int pbegin ,int pend){if(inbegin>inend||pbegin>pend)return null;TreeNode cur=new TreeNode(post[pend]);int idx=m.get(post[pend]);cur.left=tree(inbegin,idx-1,pbegin,pbegin+idx-inbegin-1);cur.right=tree(idx+1,inend,pbegin+idx-inbegin,pend-1);return cur;}
}

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

类似

java">/*** 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 {HashMap<Integer,Integer> m= new HashMap<>();int[] pre;public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++)m.put(inorder[i],i);pre=preorder;return traval(0,inorder.length-1,0,preorder.length-1);}TreeNode traval(int inbegin,int inend,int pbegin,int pend)
{if (inbegin>inend||pbegin>pend)return null;TreeNode cur=new TreeNode(pre[pbegin]);int idx=m.get(pre[pbegin]);cur.left=traval(inbegin,idx-1,pbegin+1,pbegin+idx-inbegin);cur.right=traval(idx+1,inend,pbegin+idx-inbegin+1,pend);return cur;
}
}


http://www.ppmy.cn/devtools/131265.html

相关文章

webpack5

为什么要去学习webpack 开发时可能会使用框架&#xff08;react、vue&#xff09;、ES6、less/sass等css预处理器&#xff1b; 这样的代码想要在浏览器运行必须经过编译&#xff0c;成为浏览器可以识别的js、css等语法&#xff0c;才可以运行&#xff1b; webpack用来处理以上…

146、LRU缓存-cangjie

题目 146、LRU缓存 思路 数据结构&#xff1a; 使用 HashMap (map) 存储缓存的键值对。键是缓存的键&#xff0c;值是链表节点&#xff0c;可以通过键快速访问。使用 LinkedList (lists) 来维护缓存的顺序。链表从头到尾表示使用时间&#xff0c;头部是最老的元素&#xff0c…

基于yolov5的输电线,电缆检测系统,支持图像检测,视频检测和实时摄像检测功能(pytorch框架,python源码)

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; yolov5&#xff0c;输电线(线缆)检测系统&#xff0c;系统既支持图像检测&#xff0c;也支持视频和摄像实时检测【pytorch框架】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于yolov5的输…

HarmonyOS鸿蒙开发入门,常用ArkUI组件学习(一)

刚开始接触HarmonyOS的开发&#xff0c;希望不会太晚。在我学习的过程中&#xff0c;我会将我学到的内容&#xff0c;通过写博客的形式&#xff0c;来进行回忆和复习。同时也希望能够遇到志同道合的朋友&#xff0c;我们一起学习&#xff0c;一起进步&#xff0c;文章中有什么不…

24/11/3 算法笔记 Adam优化器拆解

Adam 优化器是一种用于深度学习中的自适应学习率优化算法&#xff0c;它结合了两种其他流行的优化方法的优点&#xff1a;RMSprop 和 Momentum。简单来说&#xff0c;Adam 优化器使用了以下方法&#xff1a; 1. **指数加权移动平均&#xff08;Exponentially Weighted Moving …

利用Python进行数据可视化:实用指南与推荐库

利用Python进行数据可视化:实用指南与推荐库 数据可视化是将数据转化为图形和图表的过程,它能够帮助我们更直观地理解数据的趋势、模式和关系。在Python中,有许多强大的库可用于数据可视化,从简单的折线图到复杂的交互式图表,应有尽有。本文将详细介绍Python数据可视化的…

k8s 小版本升级

众所周知k8s每一个月左右都会更新一次小版本所以在 Kubernetes 生态系统中&#xff0c;保持集群的版本更新是至关重要的。这不仅能够带来新的特性和改进&#xff0c;还能确保集群的安全性和稳定性。随着 Kubernetes 项目的快速发展&#xff0c;小版本的升级成为了集群维护的一个…

微服务设计模式 - 网关路由模式(Gateway Routing Pattern)

微服务设计模式 - 网关路由模式&#xff08;Gateway Routing Pattern&#xff09; 定义 网关路由模式&#xff08;Gateway Routing Pattern&#xff09;是微服务架构中一种非常重要的设计模式&#xff0c;主要用于在客户端和微服务之间提供一个中间层。这一模式通过中央网关路…