数据结构 二叉树

二叉树理论基础

涵盖种类、存储、节点定义与遍历顺序等基本概念。

二叉树核心概念

• 二叉树种类与性质：包含：满二叉树节点数公式、完全二叉树定义、完全二叉树底部连续性、满二叉树必为完全二叉树、堆是完全二叉树。
• 二叉搜索树：本组介绍二叉搜索树的基本性质，包括其定义、搜索时间复杂度、节点结构灵活性、以及平衡二叉搜索树的高度约束与递归结构要求。
• STL关联容器底层：本组介绍 STL 中 map、set 及其无序变体的底层实现机制，包括所用数据结构类型、操作时间复杂度与元素排列特性。
• 二叉树存储方式：本组介绍二叉树的两种基本存储方式：链式存储与顺序存储，及其对应下标规律和适用范围。
• 二叉树结构本质：包含：二叉树可视为双指针链表、构造二叉树即构造链表。

二叉树基础精要

本组涵盖二叉树基础中的核心要点，包括遍历分类、框架、实现方式及节点定义等关键内容。

• 遍历分类与框架：包含：遍历分DFS与BFS、遍历分两大类四小类、四遍历贯穿所有题目。
• DFS与递归实现：本组讲义介绍深度优先搜索（DFS）及其递归实现方法，包括前序、中序、后序遍历的归属关系，递归作为DFS主流实现手段的原因，以及后序遍历中左右子树优先于根节点的递归结构特征。
• BFS与队列实现：本组讲义介绍广度优先搜索（BFS）在二叉树中的体现及其实现机制，重点说明层序遍历作为BFS的具体形式，以及队列在BFS迭代实现中的关键作用。
• 节点定义规范：本组内容讲解二叉树节点在代码中的标准定义方式，包括结构组成、指针含义及构造函数设计。
• 存储结构本质：本组讲解二叉树的两种存储结构本质：链式存储与顺序存储；重点阐明链式存储的组成方式及其与链表的等价关系。
• 遍历顺序由“中”位置定：二叉树的三种深度优先遍历顺序由“中”节点在序列中的位置决定。前序遍历为 中左右 ，即“中”位于序列最前； 中序遍历为 左中右 ，即“中”位于序列中间；后序遍历为 左右中 ，即“中…

递归遍历详解

动画演示前序、中序、后序递归实现与原理。

递归遍历核心机制

• 二叉树遍历四种方式：二叉树遍历的四种基本方式是前序遍历、中序遍历、后序遍历和层次遍历。 前序、中序、后序属于 深度优先遍历 ，按递归方式访问；层次遍历属于 广度优先遍历 ，按层逐层访问。
• 前序遍历规则：包含：前序遍历口诀、中序遍历顺序定义、前序遍历根节点优先、先序遍历定义、先序遍历方法、先序第一步序列。
• 前序逐层展开过程：本组内容讲解前序遍历中逐层替换的具体过程，包括第二至第五步的节点展开与最终序列生成。每一步均基于上一步结果，对某个非叶节点按其子树结构进行原位替换。
• 前序递归过程与标记法：包含：前序遍历递归过程、前序遍历标记法、遍历标记法目的。
• 中序遍历定义与处理：本组讲解中序遍历的定义规则、代码入口逻辑、无左子树节点（如C）的处理方式，以及关键节点B在中序过程中的位置判定。
• 递归代码核心要素：本组讲义系统解析递归实现中序遍历所依赖的六个核心要素：递归终止条件的判定方式、左子树遍历的调用逻辑、节点数据域的访问时机、函数返回时的回溯行为、最终形成的节点访问顺序、以及用NU…
• 遍历画点连线法：包含：前序遍历画点位置、前序遍历连线顺序、中序遍历起始节点、后序遍历补漏提示、后序遍历示例序列。
• 三序统一方法论：三序统一方法论是将前序、中序、后序遍历转化为统一图形标记的操作框架。该方法以节点为基准，在固定方位标注访问点。适用于快速推导任意二叉树的三种递归遍历序列。

二叉树遍历结果分析

二叉树遍历结果分析聚焦于不同遍历方式输出序列的构成逻辑与节点位置关系。包括对简单及复杂结构的遍历结果推导与验证。

• 层次遍历定义：层次遍历定义为将二叉树节点按 从左到右、从上到下 的顺序逐层排列。同一层内节点依左右子节点顺序排列，上层节点排在下层节点之前。该顺序不依赖递归结构，而是基于节点所在层数与层内位置。
• 简单二叉树遍历结果：简单二叉树遍历结果指仅含根节点A及其左子节点B、右子节点C的三节点树的三种遍历输出。该结构为理解遍历顺序本质的基础范例。
• 复杂二叉树遍历结果：本组讲解示例复杂二叉树的前序、中序和后序遍历结果。分别依据 根→左→右 、 左→根→右 、 左→右→根 的递归规则展开。
• G节点中序位置：G 节点在中序遍历序列中的位置，其前面是它的 左子树 H ，后面是它的 右子树 。因 G 没有右子树，故以 G 为根的子树的中序序列中 G 后面 为空 。该结论由中序遍历 左→根…

非递归遍历突破

本组内容聚焦二叉树非递归遍历的核心突破，重点解析前序与中序的迭代实现机制，揭示显式栈如何精确复现递归调用的执行顺序与节点访问时机。

递归与迭代本质

本组系统讲授二叉树前序、中序、后序及层次遍历的迭代实现细节，覆盖各遍历顺序下栈（层次遍历为队列）的操作逻辑、节点入栈出栈时机与结果数组构建过程。

• 递归与迭代本质：本组阐释递归与迭代在二叉树遍历中的内在关联：递归依赖语言底层栈，迭代则通过显式栈模拟该过程；强调面试侧重基础遍历的迭代实现，复杂递归不强制栈化。
• 前序遍历实现：本组讲解前序遍历的非递归实现原理与关键步骤，涵盖遍历顺序定义、栈结构特性、入栈策略、出栈处理逻辑及代码核心要点。
• 中序遍历特点：本组内容解析中序遍历在非递归实现中的核心特征，包括遍历顺序与处理顺序的分离性、无法通过简单调整入栈顺序实现、必须显式区分遍历路径与处理时机等关键点。
• 后序遍历技巧：本组内容介绍后序遍历迭代法的关键技巧，包括从前序代码改造的可行性、入栈顺序调整、结果数组翻转操作及对应语言库函数的使用方法。
• 迭代遍历通用要素：包含：力扣对应题目、返回类型为数组、根节点为空处理、栈存节点指针、节点结构含value。
• 迭代遍历四步框架：本组讲解非递归遍历中通用的四步操作框架：根节点入栈、以栈非空为循环条件、弹出节点、判空后处理或压栈。
• 资源与实践：本组介绍配套学习资源与实践要点：含完整可提交代码的 PDF、含经典题目的 PDF、视频配套 PDF、迭代法适用场景说明、代码可直接提交至力扣。
• 高频考点强调：包含：迭代法面试必考、递归题均可迭代解。

前序中序迭代要点

本组内容讲解二叉树前序与中序遍历的非递归实现要点，聚焦栈操作顺序、节点处理时机及访问逻辑。

• 前序迭代需先右后左入栈：前序迭代中，为使出栈顺序严格满足 中→左→右 （即根左右），必须在访问当前节点后，先将 右孩子 压入栈，再将 左孩子 压入栈。 该顺序确保左孩子位于栈顶，优先被弹出并处理。
• 栈模拟递归过程：非递归前序遍历使用显式 栈 模拟递归调用栈的行为。 每次从栈中 弹出一个节点 ，即视为完成对该节点的访问，立即加入结果数组。 随后将其非空子节点按特定顺序（右先、左后）压入栈，延…
• 叶子节点直接入结果：当弹出的节点为 叶子节点 时，其左右子节点均为空，无需压栈操作。 该节点直接加入结果数组，即完成其全部处理流程。

遍历应用与建树

本组内容聚焦于利用两种遍历序列重构二叉树的问题，核心是依据遍历顺序的结构性特征进行子树划分，并通过递归方式逐步建立节点关系。

二叉树重建方法论

本组内容系统介绍二叉树重建的方法论框架，包括根节点定位、左右子树边界判定及递归建模的基本逻辑。

• 中序后序建树原理：本组内容以中序与后序遍历序列为输入，讲解如何从序列中提取结构信息并手绘还原二叉树，强调观察位置关系与分治策略。
• 中序后序建树实践：本组内容围绕通过中序与后序遍历序列手工绘制二叉树的操作方法展开，重点讲解建树过程中的关键约束与分步执行逻辑。

画二叉树教学法

本组内容介绍面向初学者的二叉树绘制教学方法，包括操作节奏、节点展开顺序及可视化分解策略。

• 中序后序建树教学：本组内容介绍通过中序与后序遍历序列重构二叉树的基本方法，聚焦分治思想与递归建模过程。
• 层次遍历建树法：本组内容讲解利用层次遍历信息构建二叉树的具体策略，包括根据层序序列确定根节点、结合中序序列划分左右子树，以及递归构建子树的过程。