← 返回首页

第十章-二叉树和递归

第十章：二叉树和递归 (Binary Tree and Recursion)

学习内容

递归是解决二叉树问题的核心思想，理解递归思维对掌握算法至关重要。

递归思维

#### 递归三要素
1. 递归函数的参数和返回值：明确函数要处理什么，返回什么
2. 递归终止条件：防止无限递归
3. 递归单层逻辑：处理当前层的逻辑，调用递归函数处理子问题

#### 递归思维模式
1. 遍历思维：通过遍历二叉树解决问题
2. 分解思维：将问题分解为子问题，通过子问题的解构建原问题的解

二叉树算法框架

#### 基本遍历
1. 前序遍历：根左右
2. 中序遍历：左根右
3. 后序遍历：左右根

#### 层序遍历
使用队列实现，按层处理节点

常见二叉树问题

#### 二叉树路径问题



#### 二叉树构造问题



#### 二叉树属性问题



重点和难点

重点


1. 理解递归思维和递归三要素
2. 掌握二叉树遍历的各种方式
3. 熟悉常见二叉树问题的解法

难点


1. 递归思维的建立
2. 复杂递归问题的分析
3. 递归与回溯的结合使用

练习题

递归遍历题


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

2. 二叉树的直径 (Diameter of Binary Tree)
- 题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
- 解题思路：对于每个节点，计算经过该节点的最长路径（左子树深度+右子树深度），维护全局最大值。
- 注意点：直径不一定经过根节点，需要遍历所有节点。

路径问题


1. 路径总和 (Path Sum)
- 题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。
- 解题思路：递归遍历，每层递归减去当前节点值，到叶子节点时判断是否为0。
- 注意点：必须到叶子节点，不能是中间节点。

2. 二叉树中的最大路径和 (Binary Tree Maximum Path Sum)
- 题目：路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给定一个二叉树的根节点 root，返回其最大路径和。
- 解题思路：对于每个节点，计算经过该节点的最大路径和，维护全局最大值。递归函数返回以当前节点为起点向下的最大路径和。
- 注意点：路径可以不经过根节点，且可以在任意节点结束。

构造问题


1. 从前序与中序遍历序列构造二叉树 (Construct Binary Tree from Preorder and Inorder Traversal)
- 题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
- 解题思路：前序遍历的第一个元素是根节点，在中序遍历中找到根节点位置，将中序遍历分为左右子树，递归构造。
- 注意点：注意数组边界的处理，避免数组越界。

解题思路总结

递归思维的两种模式


1. 遍历模式：通过遍历二叉树，在遍历过程中处理问题
2. 分解模式：将问题分解为子问题，通过子问题的解构建原问题的解

二叉树递归的解题框架


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

处理二叉树路径问题的技巧


1. 自顶向下：从根节点开始，向叶子节点传递信息
2. 自底向上：从叶子节点开始，向根节点传递信息
3. 全局变量：使用全局变量或引用参数记录中间结果

学习时间

建议学习时间：2-3天