黑马数据结构讲义
基础数据结构-101-二叉树-概述
以下为整理后的课程文档：
━━━━━━━━━━━━━━━━━━━━
【二叉树课程文档】
━━━━━━━━━━━━━━━━━━━━
一、二叉树基本概念
1.1 定义
▫ 树型数据结构，每个节点最多有两个子节点
▫ 示例节点说明：
• 节点1、3：各有两个子节点
• 节点2：仅有一个子节点
• 节点4/5/6：无子节点（称为叶子节点）
▫ 特殊节点：
• 根节点：树的起始点（如示例中的节点1）
1.2 相关数据结构
▫ 大顶堆是特殊类型的二叉树
▫ 完全二叉树特征：
• 除最后一层外，所有层节点必须填满
• 最后一层节点必须从左向右顺序填充
• 示例说明：若节点2缺少右子节点但节点3存在左子节点，则不符合完全二叉树
二、存储方式
2.1 树节点类结构
▫ 属性组成：
• value：节点存储值
• left：左子节点（TreeNode类型）
• right：右子节点（TreeNode类型）
2.2 数组表示法
▫ 索引规则：
• 根节点：索引0
• 左子节点计算：parent_index*2 + 1
• 右子节点计算：parent_index*2 + 2
▫ 特殊处理：
• 缺失子节点可用null表示
• 示例数组[0,1,2,3,4,5,6]对应完全二叉树结构
三、遍历方法
3.1 广度优先遍历（层序遍历）
▫ 访问顺序：逐层从左到右访问
▫ 实现方式：
• 树节点结构：需配合队列实现（参考队列章节练习题）
• 数组结构：直接顺序遍历即得层序结果
▫ 访问示例：
根节点 → 2 → 3 → 4 → 5 → 6 → 7 → 8
3.2 深度优先遍历
（注：课程中未展开说明，根据上下文补充）
▫ 常见类型：
• 前序遍历：根→左→右
• 中序遍历：左→根→右
• 后序遍历：左→右→根
四、重点对比
4.1 完全二叉树 vs 普通二叉树
▫ 完全二叉树要求：
• 除末层外各层满节点
• 末层节点左对齐
▫ 普通二叉树：
• 允许任意位置空缺子节点
4.2 存储方式对比
│ 特性 │ 树节点类 │ 数组表示 │
├───────────┼─────────────────┼─────────────┤
│ 内存效率 │ 动态分配更灵活 │ 适合满二叉树 │
│ 空值处理 │ 自然表示 │ 需占位符 │
│ 遍历便利性 │ 需递归/栈/队列 │ 天然层序结构 │
五、应用场景
▫ 优先级队列（堆结构）
▫ 表达式树
▫ 文件系统目录结构
▫ 数据库索引（B树/B+树基础）
━━━━━━━━━━━━━━━━━━━━
注：文档已修正原录音中"TreeNode"误转为"TRAINNO"、"层序遍历"误为"程序遍历"等错别字，并优化了技术表述的准确性。
基础数据结构-102-二叉树-深度优先遍历
以下是整理后的课程文档，已修正错别字并优化内容结构：
二叉树深度优先遍历详解
一、深度优先遍历概述
二叉树深度优先遍历分为三种类型：
- 前序遍历（Pre-order）
- 中序遍历（In-order）
- 后序遍历（Post-order）
共同特点：优先深入访问距离根节点最远的叶子节点
二、动画工具使用说明
数据结构表示：使用数组存储二叉树结构
• 根节点索引：0• 子节点位置：左子节点 = 2n+1，右子节点 = 2n+2
• None 表示空节点
操作指南：
• 修改数组后点击"保存"更新树形结构• 节点颜色标识：
◦ 灰色：未访问节点
◦ 绿色：已访问节点
示例操作：
# 初始数组 [1, 2, 3, 4, None, 5, 6]• 修改节点4的子节点为7,8 → 数组更新为
[1,2,3,4,None,5,6,7,8]
三、遍历规则详解
- 前序遍历（根-左-右）
规则： - 访问当前节点值
- 递归遍历左子树
- 递归遍历右子树
示例流程（数组 [1,2,3,4,None,5,6]）：
访问根 → 1
遍历左子树（2,4）：
访问2 → 1,2
遍历左子树（4）→ 1,2,4
遍历右子树（3,5,6）：
访问3 → 1,2,4,3
遍历左子树（5）→ 1,2,4,3,5
遍历右子树（6）→ 1,2,4,3,5,6结果：1→2→4→3→5→6
- 中序遍历（左-根-右）
规则： - 递归遍历左子树
- 访问当前节点值
- 递归遍历右子树
示例流程：
遍历左子树（2,4）：
遍历左子树（4）→ 4
访问2 → 4,2
访问根 → 4,2,1
遍历右子树（3,5,6）：
遍历左子树（5）→ 5
访问3 → 5,3
遍历右子树（6）→ 5,3,6结果：4→2→1→5→3→6
- 后序遍历（左-右-根）
规则： - 递归遍历左子树
- 递归遍历右子树
- 访问当前节点值
示例流程：
遍历左子树（2,4）：
访问4 → 4
访问2 → 4,2
遍历右子树（3,5,6）：
遍历左子树（5）→ 5
遍历右子树（6）→ 6
访问3 → 5,6,3
访问根 → 4,2,5,6,3,1结果：4→2→5→6→3→1
四、三种遍历对比
| 遍历类型 | 访问顺序 | 记忆口诀 | 典型应用场景 |
|---|---|---|---|
| 前序遍历 | 根节点 → 左 → 右 | 根左右 | 复制树结构、前缀表达式 |
| 中序遍历 | 左 → 根节点 → 右 | 左根右 | 二叉搜索树有序输出 |
| 后序遍历 | 左 → 右 → 根节点 | 左右根 | 释放内存、后缀表达式 |
五、核心要点总结
递归本质：三种遍历均采用深度优先的递归策略
规则差异：
• 前序：第一时间处理根节点• 中序：在左右子树间处理根节点
• 后序：最后处理根节点
实践要求：需能根据树形结构快速推导遍历序列
提示：建议结合树形结构进行手动画图练习，强化遍历顺序的记忆和理解。
基础数据结构-103-二叉树-前中后遍历-递归实现
以下是整理后的课程文档，已修正错别字并优化表述：
二叉树遍历的代码实现（递归与非递归）
目录
树节点的构造
示例树的构建
递归遍历实现
• 前序遍历• 中序遍历
• 后序遍历
代码测试与输出结果
- 树节点的构造
使用TreeNode类表示树节点：
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value # 节点值
self.left = left # 左子节点
self.right = right # 右子节点- 示例树的构建
构造与课程示例相同的二叉树：
1
/ \
2 3
/ / \
4 5 6构建代码：
# 叶子节点（无子节点）
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
# 中间节点
node2 = TreeNode(2, node4, None) # 左子节点为4，无右子节点
node3 = TreeNode(3, node5, node6)
# 根节点
root = TreeNode(1, node2, node3)- 递归遍历实现
3.1 前序遍历（根-左-右）
实现逻辑：
- 访问当前节点值
- 递归处理左子树
- 递归处理右子树
def pre_order(node):
if node is None:
return
print(node.value, end=" ") # 先访问当前节点
pre_order(node.left) # 递归左子树
pre_order(node.right) # 递归右子树3.2 中序遍历（左-根-右）
实现逻辑：
- 递归处理左子树
- 访问当前节点值
- 递归处理右子树
def in_order(node):
if node is None:
return
in_order(node.left) # 递归左子树
print(node.value, end=" ") # 中间访问当前节点
in_order(node.right) # 递归右子树3.3 后序遍历（左-右-根）
实现逻辑：
- 递归处理左子树
- 递归处理右子树
- 访问当前节点值
def post_order(node):
if node is None:
return
post_order(node.left) # 递归左子树
post_order(node.right) # 递归右子树
print(node.value, end=" ") # 最后访问当前节点- 代码测试与输出结果
测试代码
print("前序遍历结果：", end="")
pre_order(root)
print("\n中序遍历结果：", end="")
in_order(root)
print("\n后序遍历结果：", end="")
post_order(root)输出结果
前序遍历结果：1 2 4 3 5 6
中序遍历结果：4 2 1 5 3 6
后序遍历结果：4 2 5 6 3 1关键点说明
递归终止条件：当节点为
None时停止递归访问顺序差异：
• 前序：先访问当前节点，再处理子树• 中序：先处理左子树，再访问当前节点
• 后序：先处理子树，最后访问当前节点
时间复杂度：均为 O(n)，每个节点访问一次
空间复杂度：递归栈深度为树的高度，最差情况（链状树）为 O(n)
后续课程可继续讲解非递归（迭代）实现方式，借助栈/队列等数据结构完成遍历。
基础数据结构-104-二叉树-前中后遍历-非递归1
二叉树非递归遍历算法详解
一、遍历路径的共性分析
前序、中序、后序遍历路径完全一致：
• 路径：1 → 2 → 4 → 返回2 → 返回1 → 3 → 5 → 返回3 → 6 → 返回3 → 返回1访问时机的差异：
• 前序：首次到达节点时访问• 中序：返回至节点时访问
• 后序：最后一次离开节点时访问
二、核心数据结构设计
使用栈记录遍历路径
• 初始化空栈（LinkedList实现）• 当前指针current初始化为根节点
循环控制条件：
while (current != null || !stack.isEmpty())
三、非递归遍历算法实现步骤
- 左子树深度遍历
// 深度优先遍历左子树
while (current != null) {
System.out.println("去: " + current.val); // 前序遍历访问点
stack.push(current);
current = current.left;
}- 回溯处理右子树
// 回溯处理右子树
current = stack.pop();
System.out.println("回: " + current.val); // 中序遍历访问点
current = current.right; // 转向右子树- 完整遍历流程示例
以示例树结构：
1
/ \
2 3
/ / \
4 5 6遍历轨迹：
去1 → 去2 → 去4 → 回4 → 回2 → 回1 → 去3 → 去5 → 回5 → 回3 → 去6 → 回6 → 回3四、不同遍历类型的实现调整
- 前序遍历：
System.out.println("前序: " + current.val); // 在"去"阶段访问 - 中序遍历：
System.out.println("中序: " + current.val); // 在"回"阶段访问 - 后序遍历：
// 需要额外记录访问状态 while (current != null || !stack.isEmpty()) { while (current != null) { stack.push(current); current = current.left; } current = stack.pop(); if (current.right == null || lastVisited == current.right) { System.out.println("后序: " + current.val); lastVisited = current; current = null; } else { stack.push(current); current = current.right; } }
五、关键问题解析
路径回溯机制：
• 利用栈FILO特性逆向回溯访问路径• 每次弹出栈顶元素即返回至父节点
时间复杂度分析：
• 时间复杂度：O(n)• 空间复杂度：O(h)，h为树的高度
非递归优势：
• 避免递归栈溢出• 更灵活控制遍历过程
• 便于实现复杂遍历逻辑
六、算法扩展应用
- 层序遍历（使用队列）
- 锯齿形遍历（双栈交替）
- 线索二叉树遍历
- 迭代式深度克隆
- 边界节点遍历
掌握非递归遍历的核心在于理解栈在模拟递归调用栈中的作用，通过调整节点访问时机即可实现不同遍历顺序。这种实现方式为更复杂的树操作（如序列化、平衡检查等）奠定了基础。
基础数据结构-105-二叉树-前中后遍历-非递归2
以下是整理后的课程文档（已修正错别字并优化表述）：
二叉树遍历算法详解（前序/中序）
代码功能概述
本课程演示了使用栈结构实现二叉树前序和中序遍历的统一算法框架，并通过彩色控制台输出直观展示遍历路径差异。
颜色标记打印方法
实现方案
# 示例代码片段（关键部分）
def color_print(text, color_code):
print(f"\033[{color_code}m{text}\033[0m")
# 前序打印（红色）
color_print(current.val, 31) # 31为红色代码
# 中序打印（蓝色）
color_print(current.val, 34) # 34为蓝色代码颜色规范
• 红色（31）：表示"去程"操作，对应前序遍历的节点访问
• 蓝色（34）：表示"回程"操作，对应中序遍历的节点访问
前序遍历执行流程解析
算法规则
遵循"根→左→右"（Root→Left→Right）顺序
执行步骤
初始化栈并设定根节点为当前节点
循环处理：
a. 当存在左子树时：
◦ 立即打印当前节点（红色）◦ 压栈保存访问路径
◦ 持续向左子树深入
b. 当左子树为空时：
◦ 弹栈回溯访问路径◦ 检查并处理右子树
完整遍历顺序：
1 → 2 → 4 → 3 → 5 → 6
栈操作示例
| 步骤 | 当前节点 | 操作 | 栈状态 | 输出 |
|---|---|---|---|---|
| 1 | 1 | 打印后压栈 | [1] | 1(红) |
| 2 | 2 | 打印后压栈 | [1,2] | 2(红) |
| 3 | 4 | 打印后压栈 | [1,2,4] | 4(红) |
| 4 | None | 弹栈→4 | [1,2] | |
| 5 | None | 弹栈→2 | [1] | |
| 6 | 3 | 打印后压栈 | [1,3] | 3(红) |
| 7 | 5 | 打印后压栈 | [1,3,5] | 5(红) |
| 8 | None | 弹栈→5 | [1,3] | |
| 9 | None | 弹栈→3 | [1] | |
| 10 | 6 | 打印 | [] | 6(红) |
中序遍历执行流程解析
算法规则
遵循"左→根→右"（Left→Root→Right）顺序
执行步骤
- 初始化栈并持续向左子树深入
- 当左子树为空时开始回溯：
a. 弹栈获取最近节点
b. 打印当前节点（蓝色）
c. 转向处理右子树 - 完整遍历顺序：
4 → 2 → 1 → 5 → 3 → 6
核心差异点
• 打印时机：在左子树完全处理完成后进行
• 栈操作：节点在弹栈时执行打印
代码切换说明
# 前序遍历模式（注释回程打印）
def pre_order(root):
while ...:
if current:
color_print(current.val, 31) # 保持此行
# color_print(current.val, 34) # 注释此行
# 中序遍历模式（注释去程打印）
def in_order(root):
while ...:
if current:
# color_print(current.val, 31) # 注释此行
color_print(current.val, 34) # 保持此行算法流程对比
| 特征 | 前序遍历 | 中序遍历 |
|---|---|---|
| 打印时机 | 首次访问节点时 | 回溯访问节点时 |
| 栈存储目的 | 记录未处理右子树的节点 | 记录待打印的父节点 |
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(h)（h为树高度） | O(h) |
| 典型应用场景 | 复制树结构 | 二叉搜索树有序输出 |
教学总结
通过栈结构实现非递归遍历，避免递归的栈溢出风险
彩色打印直观展示遍历路线差异：
• 红色路径对应深度优先的"去程"操作• 蓝色路径对应回溯的"回程"操作
统一代码框架通过简单注释切换即可实现不同遍历方式
重点理解节点访问时机与栈操作的配合关系
基础数据结构-106-二叉树-前中后遍历-非递归3
以下是经过整理的课程文档（已修正错别字并优化表述）：
二叉树后序遍历的非递归实现详解
一、遍历方式对比
- 前序遍历
• 访问顺序：根节点 → 左子树 → 右子树
• 弹栈逻辑：访问后立即弹栈
- 中序遍历
• 访问顺序：左子树 → 根节点 → 右子树
• 弹栈逻辑：左子树处理完成后弹栈
- 后序遍历（核心重点）
• 访问顺序：左子树 → 右子树 → 根节点
• 弹栈逻辑：必须等待左右子树都处理完成才能弹栈
二、中序遍历实现逻辑（对比基础）
压栈过程：沿左子树路径持续压栈至最左节点
弹栈时机：
• 当左子树处理完成（到达叶子节点）• 立即弹栈并访问节点
右子树处理：
current = stack.pop() print(current.val) current = current.right
三、后序遍历关键难点
核心矛盾：
• 节点必须保留在栈中直到右子树处理完成
• 需要记录右子树处理状态
解决方案：
新增状态记录：
last_pop = None # 记录最近弹栈节点双重判断条件：
• 当栈顶元素满足以下任一条件时可弹栈：if (peek.right is None) or (peek.right == last_pop):
四、后序遍历实现步骤
算法流程：
- 初始化：
stack = [] current = root last_pop = None - 左子树压栈：
while current: stack.append(current) current = current.left - 栈处理循环：
while stack: peek = stack[-1] # 查看栈顶元素 # 满足弹栈条件 if peek.right is None or peek.right == last_pop: last_pop = stack.pop() print(last_pop.val) # 未满足则处理右子树 else: current = peek.right while current: stack.append(current) current = current.left
五、执行过程示例（以树1-2-3-4-5-6-7为例）
- 压栈路径：
1 → 2 → 4（最左节点） - 弹栈顺序：
4（右空） → 2（等待7处理） → 7 → 2 → 5 → 6 → 3 → 1 - 最终输出：
4 7 2 5 6 3 1
六、与前/中序遍历的核心差异
| 特征 | 前序遍历 | 中序遍历 | 后序遍历 |
|---|---|---|---|
| 访问顺序 | 根-左-右 | 左-根-右 | 左-右-根 |
| 首次访问时机 | 压栈前 | 弹栈后 | 弹栈后 |
| 弹栈条件 | 立即弹栈 | 左子树完成 | 左右子树均完成 |
| 状态记录 | 无需 | 无需 | 需要last_pop记录 |
七、常见问题解答
Q：为什么需要记录last_pop？
A：用于验证当前节点的右子树是否已处理：
• 当peek.right == last_pop成立时，说明右子树已处理完成
Q：如何处理右子树为空的节点？
A：直接满足peek.right is None条件，可立即弹栈访问
Q：时间复杂度如何？
A：O(n)，每个节点恰好经历1次压栈和1次弹栈操作
此文档已修正原始录音中的术语错误（如"弹战"→"弹栈"、"变量"→"遍历"等），并优化了算法逻辑的表述层次。
基础数据结构-107-二叉树-前中后遍历-非递归4
二叉树非递归遍历的统一实现方法课程文档
一、非递归遍历代码的演进思路
- 前序、中序遍历代码结构高度相似（仅打印位置不同）
- 后序遍历代码路径最完整（完整绕树遍历）
- 改造思路：基于后序遍历代码模板进行统一改造，通过控制打印时机实现三种遍历
二、后序遍历基础模板解析
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
TreeNode pop = null;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
// 待处理左子树
current = current.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
pop = stack.pop();
}
// 右子树处理完成
else if (peek.right == pop) {
pop = stack.pop();
}
// 待处理右子树
else {
current = peek.right;
}
}
}三、遍历时机与代码插入位置
- 前序遍历（值左右）
// 在处理左子树前插入
result.add(current.val); // 前序插入点
current = current.left;- 中序遍历（左值右）
// 左子树处理完成后，处理右子树前
TreeNode peek = stack.peek();
// 情况1：没有右子树时
if (peek.right == null) {
result.add(peek.val); // 中序插入点1
}
// 情况2：处理右子树前
else {
result.add(peek.val); // 中序插入点2
current = peek.right;
}- 后序遍历（左右值）
// 在节点弹出栈后插入
if (peek.right == null) {
pop = stack.pop();
result.add(pop.val); // 后序插入点1
}
else if (peek.right == pop) {
pop = stack.pop();
result.add(pop.val); // 后序插入点2
}四、统一实现模板代码（Java）
public List<Integer> traversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
TreeNode pop = null;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
// 前序遍历插入点
// result.add(current.val);
current = current.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null) {
// 中序遍历插入点1
// result.add(peek.val);
pop = stack.pop();
// 后序遍历插入点1
// result.add(pop.val);
} else if (peek.right == pop) {
pop = stack.pop();
// 后序遍历插入点2
// result.add(pop.val);
} else {
// 中序遍历插入点2
// result.add(peek.val);
current = peek.right;
}
}
}
return result;
}五、LeetCode题解实现144. 二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
if (current != null) {
result.add(current.val); // 前序插入点
stack.push(current);
current = current.left;
} else {
TreeNode node = stack.pop();
current = node.right;
}
}
return result;
}
}- 二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
TreeNode pop = null;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null) {
result.add(peek.val);
pop = stack.pop();
} else if (peek.right == pop) {
pop = stack.pop();
} else {
result.add(peek.val);
current = peek.right;
}
}
}
return result;
}
}- 二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
TreeNode pop = null;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null) {
pop = stack.pop();
result.add(pop.val);
} else if (peek.right == pop) {
pop = stack.pop();
result.add(pop.val);
} else {
current = peek.right;
}
}
}
return result;
}
}六、核心要点总结
遍历路径：后序遍历路径最完整，适合作为基础模板
打印时机：
• 前序：首次访问节点时（处理左子树前）• 中序：左子树处理完成后，处理右子树前
• 后序：节点最后一次出栈时（左右子树均处理完成）
栈操作：
• push：往左子树深入• pop：子树处理完成回溯
复杂度：时间复杂度O(n)，空间复杂度O(h)（h为树高）
注：本实现通过统一模板可减少记忆负担，建议通过画图辅助理解不同遍历的节点访问顺序。实际面试中可根据题目要求选择具体的遍历实现方式。
基础数据结构-108-二叉树-e04-对称二叉树
对称二叉树算法详解
一、问题描述
给定一棵二叉树，检查其是否轴对称（镜像对称）。即左子树与右子树以根节点为对称轴形成镜像对称关系。
二、算法思路
采用递归法判断左右子树是否对称，遵循以下判断逻辑：
根节点处理
• 根节点为空时视为对称• 根节点非空时检查其左右子树
递归判断逻辑
定义递归函数check(left, right)判断两个节点是否对称：
• 基线条件◦ 两个节点均为空 → 对称
◦ 一个为空一个非空 → 不对称
• 值比较
◦ 节点值不等 → 不对称
• 递归比较
◦ 外层比较：左节点的左子树 vs 右节点的右子树
◦ 内层比较：左节点的右子树 vs 右节点的左子树
三、代码实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root: TreeNode) -> bool:
if not root:
return True
return check(root.left, root.right)
def check(left: TreeNode, right: TreeNode) -> bool:
# 同时为空
if not left and not right:
return True
# 存在单个节点为空
if not left or not right:
return False
# 节点值不相等
if left.val != right.val:
return False
# 递归检查子节点
return check(left.left, right.right) and check(left.right, right.left)四、算法分析
时间复杂度
每个节点访问一次，时间复杂度为 O(n)
空间复杂度
递归调用栈深度最大为树高：
• 最优情况（平衡树）：O(log n)
• 最差情况（链状树）：O(n)
五、测试用例
# 对称用例
# 1
# / \
# 2 2
# / \ / \
# 3 4 4 3
root1 = TreeNode(1,
TreeNode(2, TreeNode(3), TreeNode(4)),
TreeNode(2, TreeNode(4), TreeNode(3)))
print(isSymmetric(root1)) # True
# 非对称用例
# 1
# / \
# 2 2
# \ \
# 3 3
root2 = TreeNode(1,
TreeNode(2, None, TreeNode(3)),
TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root2)) # False六、关键点说明
递归终止条件：正确处理空节点情况是算法正确性的基础
镜像比较规则：
• 左子树的左节点对应右子树的右节点• 左子树的右节点对应右子树的左节点
剪枝优化：当发现节点值不等时立即终止递归，提升算法效率
通过递归实现的镜像对称检查，能够高效判断二叉树的对称性，代码简洁且符合树结构的遍历特性。
基础数据结构-109-二叉树-e05-最大深度-解法1
LeetCode 104. 二叉树的最大深度 课程文档
目录
题目描述
深度定义
• 教材定义 vs LeetCode定义解题思路
• 递归法• 后序遍历思想
代码实现
测试用例验证
注意事项
复杂度分析
- 题目描述
给定一个二叉树，找出其最大深度（从根节点到最远叶子节点的最长路径长度）。
- 深度定义
教材定义
• 深度 = 根节点到最远节点路径的边数
• 示例：
• 单层树（仅根节点）：深度为 0
• 根节点带一个子节点：深度为 1（边数）
LeetCode定义
• 深度 = 根节点到最远节点路径的节点数
• 即教材深度值 +1
• 示例：
• 单层树：深度为 1
• 根节点带一个子节点：深度为 2
- 解题思路
递归法（分治思想）
核心逻辑：
- 当前节点深度 = max(左子树深度, 右子树深度) + 1
- 递归终止条件：空节点深度为 0
后序遍历应用：
• 先计算左右子树深度（左→右→根的顺序）
• 每个节点的处理依赖子树结果
- 代码实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1代码解析：
• if not root 处理空节点，返回深度 0
• 递归计算左右子树深度
• 返回较大子树深度 +1（当前层贡献）
- 测试用例验证
| 测试用例 | 树结构 | 预期结果 | 实际结果 |
|---|---|---|---|
| 1 | [1,2,3] | 2（节点数） | ✅ 通过 |
| 2 | [1,2,null,3,null,4] | 3 | ✅ 通过 |
| 3 | [1] | 1 | ✅ 通过 |
注意事项
叶子节点处理优化：
• 显式判断叶子节点（左右子为空）可省略• 递归逻辑自动处理：空子节点返回0，max(0,0)+1=1
定义统一性：
• 需明确题目要求的深度计算方式（LeetCode标准）
- 复杂度分析
• 时间复杂度：O(n)
每个节点访问一次
• 空间复杂度：O(h)
h为树高，递归栈空间消耗
最坏情况（链状树）：O(n)
平衡树情况：O(log n)
关键点总结：
- 递归分治思想的应用
- 后序遍历的典型场景
- 空节点与叶子节点的统一处理
- 定义差异的明确理解
通过此方法可高效解决二叉树深度类问题，该思路也可扩展至其他树相关题目（如最小深度、对称树判断等）。
基础数据结构-110-二叉树-e05-最大深度-解法2
二叉树最大深度的非递归后序遍历解法（修正版）
解题思路分析
核心思想
通过非递归方式的后续遍历，在遍历过程中记录栈的最大深度，该深度即为二叉树的最大深度。
后序遍历特性
- 遍历顺序：左子树 -> 右子树 -> 根节点
- 栈的特性：先进后出，用于记录遍历路径
- 关键观察：栈的深度在遍历过程中动态变化，其最大值对应树的最大深度
算法流程
初始化当前节点为根节点，创建空栈和最大深度记录变量
左子树深度遍历：
• 沿左子树不断压栈，直到叶子节点• 此时栈深度即为当前路径深度
右子树处理：
• 当左子树处理完毕后，检查右子树是否已处理• 未处理则转向右子树继续深度遍历
栈深度监控：
• 每次压栈后立即检查当前栈深度• 动态更新最大深度值
代码实现（Java）
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
TreeNode current = root;
TreeNode pop = null; // 记录最近弹栈节点
LinkedList<TreeNode> stack = new LinkedList<>();
int maxDepth = 0;
while (current != null || !stack.isEmpty()) {
// 深度优先处理左子树
if (current != null) {
stack.push(current);
current = current.left;
// 更新最大深度
maxDepth = Math.max(maxDepth, stack.size());
} else {
// 获取栈顶元素（不弹出）
TreeNode peek = stack.peek();
// 右子树处理逻辑
if (peek.right == null || peek.right == pop) {
// 后序遍历处理根节点
pop = stack.pop();
} else {
// 转向右子树
current = peek.right;
}
}
}
return maxDepth;
}
}关键逻辑解析
栈深度监控机制
// 压栈后立即检查深度
stack.push(current);
current = current.left;
maxDepth = Math.max(maxDepth, stack.size());右子树处理条件
// 满足以下条件之一即可弹栈：
// 1. 无右子树
// 2. 右子树已处理完毕（通过pop指针验证）
if (peek.right == null || peek.right == pop)循环终止条件
// 同时满足：
// 1. 当前节点为空（遍历到底部）
// 2. 栈已清空（遍历完成）
while (current != null || !stack.isEmpty())复杂度分析
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要完整遍历所有节点 |
| 空间复杂度 | O(h) | 栈深度最大为树的高度 |
测试验证
测试用例设计
- 空树：返回0
- 单节点树：返回1
- 完全二叉树（示例树）：返回4
示例树遍历过程
1
/ \
2 5
/ \
4 7遍历路径：
- 1->2->4（栈深3）
- 回退处理右子树
- 1->5->7（栈深3→4）
- 最终最大深度：4
方案优劣对比
优势
- 无需递归调用栈
- 显式控制遍历过程
- 空间效率与树高度相关
劣势
- 实现复杂度高于递归
- 需要维护额外状态（pop指针）
- 实际运行效率可能略低于递归解法
补充说明
该方法通过改造标准后序遍历算法，在遍历过程中动态监控栈深度的变化，巧妙地将遍历过程与深度计算结合。虽然时间复杂度与递归解法相同，但为处理二叉树问题提供了不同的视角，有助于加深对遍历算法和栈操作的理解。