【LeetCode经典题解】：从前序和中序遍历构建二叉树详解

Ne0inhk

— 4 min read
【LeetCode经典题解】：从前序和中序遍历构建二叉树详解
在这里插入图片描述
🎁个人主页：User_芊芊君子
🎉欢迎大家点赞👍评论📝收藏⭐文章
🔍系列专栏：Java.数据结构
在这里插入图片描述


在这里插入图片描述

【前言】

二叉树构造是算法中递归分治思想的经典应用，而通过前序与中序遍历序列还原二叉树，更是力扣考察二叉树特性的高频题。前序“根左右”、中序“左根右”的遍历特性，是逐层确定根节点、划分左右子树的关键。本文将从递归分治思想出发，拆解该问题的实现逻辑，分析代码设计的核心细节。

文章目录：

一、从前序遍历和中序遍历构造二叉树

链接直达：从前序遍历和中序遍历构造二叉树

在这里插入图片描述

二、思路分析

根据递归分治思想：

前序遍历：根节点—>左子树—>右子树；找到前序序列的第一个元素就是根节点；中序遍历：左子树—>根节点—>右子树；找到根节点在中序序列中的位置，从而确定左子树和右子树；递归处理：重复上面的步骤，依次确定子树的根节点并构建子树，直至子树为空。

三、代码详解

1.代码分析

  • preorder：前序遍历数组；
  • inorder : 中序遍历数组；
  • 成员变量 preIndex : 用于记录前序遍历中当前根节点的索引 （通过通过全局递增依次取前序序列的根节点）
  • findVal 方法：查找根节点在中序序列中的索引rootIndex；
  • 递归方法buildTreeChild ：
递归终止条件：当 inbegin>inend ，说明当前子树无节点，返回null;构建根节点，取前序数组preIndex位置的元素作为根节点；划分左右子树，通过findVal方法找到根节点在中序序列中的索引rootIndex，inbegin ~ rootIndex-1为左子树，rootIndex+1 ~ inend为右子树

2.代码展示

publicint preIndex;publicTreeNodebuildTree(int[] preorder,int[] inorder){returnbuildTreeChild(preorder, inorder,0,inorder.length-1);}publicintfindVal(int[] inorder,int inbegin,int inend,int key){for(int i = inbegin;i<=inend;i++){if(inorder[i]==key){return i;}}return-1;}publicTreeNodebuildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){//递归终止条件：当前子树中序区间无节点if(inbegin>inend){returnnull;}//前序序列Index位置作为根节点TreeNode root =newTreeNode(preorder[preIndex]);//在中序序列中找到根节点的索引int rootIndex =findVal(inorder,inbegin,inend,preorder[preIndex]);//preIndex递增，指向下一个子树根节点 preIndex++;//递归左子树，范围：inbegin ~ rootIndex-1 root.left =buildTreeChild(preorder,inorder,inbegin,rootIndex-1);//递归左子树，范围：rootIndex+1 ~ inend root.right =buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}

【总结】

本文围绕前序+中序构建二叉树问题，解析了递归分治的解题思路：依托前序确定根节点，通过中序划分左右子树区间，再递归构建子树至区间为空。代码中用 prIndex 追踪前序根节点位置，借 findVal定位中序根节点索引完成边界划分，核心是对遍历特性的运用与递归终止条件的设置。此外，还可通过哈希表优化中序查找效率，该思路也为后序+中序构建二叉树等同类问题提供了参考。
在这里插入图片描述

Read more

Redis Hash 全解析：从入门到精通，解锁高性能对象存储的钥匙

Redis Hash 全解析：从入门到精通，解锁高性能对象存储的钥匙

前言 在现代应用开发中，我们无时无刻不在与“对象”打交道——用户信息、商品详情、配置项、会话数据……如何高效、清晰地在缓存或数据库中存储这些结构化数据，是每一个开发者都需要面对的课题。 你可能会想到将一个对象序列化成 JSON 字符串，然后用一个简单的 Key-Value 方式存入 Redis。这确实是一种方法，但当你只想修改对象的某一个属性（比如用户的积分）时，就不得不读取整个 JSON 字符串，反序列化成对象，修改属性，再序列化回 JSON，最后整个写回 Redis。这个过程不仅繁琐，而且在并发环境下极易引发数据覆盖问题，性能开销也相当可观。 那么，有没有一种更原生、更高效的方式来处理这种“对象”存储呢？答案是肯定的。Redis 为我们提供了一种强大的数据结构，它天生就是为了解决这类问题而生——Hash（哈希/散列）。 本文将带领你深入探索 Redis Hash

By Ne0inhk
数据结构【AVL树】

数据结构【AVL树】

AVL树 * 1.AVL树 * 1.1AVL的概念 * 1.2平衡因子 * 2.AVl树的实现 * 2.1AVL树的结构 * 2.2AVL树的插入 * 2.3 旋转 * 2.3.1 旋转的原则 1.AVL树 1.1AVL的概念 AVL树可以是一个空树。 它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。 AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN ，那么增删查改的效率也可以控制在O(logN ) ，相比二叉搜索树有了本质的提升。 1.2平衡因子 结点的平衡因子=右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标一样。 为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？ 因为例如二和四个结点无法达到0.

By Ne0inhk
玩转二叉树:数据结构中的经典之作

玩转二叉树:数据结构中的经典之作

、 嘿嘿,家人们,今天咱们来详细剖析数据结构中的二叉树,好啦,废话不多讲,开干! 1:树的概念以及结构 1.1:树的概念 1.2:树的相关概念 1.3:树的表示 1.3.1:左孩子右兄弟表示法 2:二叉树的概念以及结构 2.1:概念 2.2:特殊的二叉树 2.3:二叉树的性质 2.4:二叉树的存储结构 2.4.1:顺序存储 2.4.2:链式存储 3:二叉树的顺序结构以及实现 3.1:二叉树的顺序结构 3.2:

By Ne0inhk