← 返回首页

第三章-二叉树

第三章：二叉树 (Binary Trees)

学习内容

二叉树是树形数据结构中最基础和最重要的结构之一，是理解递归思维的关键。

二叉树基础

二叉树是每个节点最多有两个子树的树结构，通常子树被称作"左子树"和"右子树"。

#### 常见类型
1. 满二叉树：除最后一层无任何节点外，每一层上的所有节点都有两个子节点的二叉树
2. 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
3. 二叉搜索树：左子树上所有结点的值均小于它的根节点的值，右子树上所有结点的值均大于它的根节点的值
4. 平衡二叉树：左右两个子树的高度差的绝对值不超过1

二叉树遍历

#### 递归遍历
1. 前序遍历：根节点 → 左子树 → 右子树
2. 中序遍历：左子树 → 根节点 → 右子树
3. 后序遍历：左子树 → 右子树 → 根节点

#### 层序遍历
使用队列实现，按层级从左到右访问节点。

多叉树遍历

多叉树的遍历与二叉树类似，但需要遍历所有子节点。

重点和难点

重点


1. 理解二叉树的基本概念和性质
2. 掌握二叉树的各种遍历方法
3. 理解递归在树结构中的应用

难点


1. 递归思维的建立
2. 非递归遍历的实现
3. 树的构造问题

练习题

遍历相关


1. 二叉树的中序遍历 (Binary Tree Inorder Traversal)
- 题目：给定一个二叉树的根节点 root ，返回它的中序遍历。
- 解题思路：递归方法直接实现中序遍历；迭代方法使用栈模拟递归过程。
- 注意点：递归方法简单直观，迭代方法需要理解栈的使用。

2. 二叉树的层序遍历 (Binary Tree Level Order Traversal)
- 题目：给你一个二叉树，请你返回其按层序遍历得到的节点值。
- 解题思路：使用队列进行广度优先搜索，记录每层节点数量。
- 注意点：需要区分每一层的节点。

递归相关


1. 最大深度 (Maximum Depth of Binary Tree)
- 题目：给定一个二叉树，找出其最大深度。
- 解题思路：递归计算左右子树的最大深度，取较大值加1。
- 注意点：处理空节点的边界情况。

2. 对称二叉树 (Symmetric Tree)
- 题目：给定一个二叉树，检查它是否是镜像对称的。
- 解题思路：递归比较左子树和右子树是否镜像对称。
- 注意点：需要定义辅助函数比较两个子树。

解题思路总结

DFS vs BFS 适用场景



递归思维模式


1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑

层序遍历的三种写法模板


1. 基础模板：使用队列进行层序遍历
2. 记录层数模板：在基础模板上增加层数信息
3. 从右到左遍历模板：调整入队顺序实现反向遍历

学习时间

建议学习时间：1-2天