代码随想录算法训练营第21天｜二叉树Part08

二叉树总结篇。

遍历方式总结

深度优先遍历（DFS）

• 递归方式：前序（中左右）、中序（左中右）、后序（左右中）
• 迭代方式：使用栈模拟递归，适用于三种顺序

广度优先遍历（BFS）

• 使用队列进行层序遍历
• 可拓展为“每层最大值”“之字形遍历”“最后一层左/右值”等题型

二叉树基本属性问题

题目	解法思路	遍历顺序
0101. 对称二叉树	递归比对左右子树是否对称； 队列模拟同步遍历	后序（递归） / 层序
0104. 二叉树的最大深度	返回左右子树最大高度 + 1	后序 / 层序
0111. 二叉树的最小深度	注意忽略不存在的子树	后序 / 层序
0222. 完全二叉树的节点个数	后序递归， 或利用完全树高度差剪枝	后序
0110. 平衡二叉树	返回高度同时判断是否失衡	后序
0513. 找树左下角的值	层序遍历记录每层第一个节点； 或 DFS 记录最深层左值	层序 or DFS
0404. 左叶子之和	判断左子节点是否是叶子并累加	后序 / 层序
0112. 路径总和	路径累计判断等于目标值	DFS + 回溯 / 栈辅助

一般来说，求“树的整体属性”（如深度、是否平衡、节点数等）适合后序遍历，因为需要依赖子树返回值。

路径型问题（含回溯）

题目	解法思路	说明
0257. 二叉树的所有路径	前序递归记录路径 + 回溯	构建路径字符串，回溯撤销路径
0113. 路径总和 II	前序递归 + 路径数组 + 回溯	找出所有路径和等于目标值的路径
0437. 路径总和 III	DFS + 前缀和 + 回溯	路径不限起点，使用前缀和优化
0129. 求根到叶子节点数字之和	前序递归记录数字路径 + 回溯	将路径数字转为整数求和
0112. 路径总和	递归判断是否存在路径和	返回bool，判断是否存在目标路径

虽然有些路径题目并未提及回溯，但本质就是回溯模式。 路径类问题处理策略通常是：前序遍历 + 路径回退。 此外有时候路径回退是可以隐藏在递归参数传递中的。

构造与修改问题

题目	解法思路	说明
0226. 翻转二叉树	交换左右子树指针	前序 or 层序
0106. 从中序与后序遍历构造二叉树	找到中间点递归构造左右子树	分治 + 前序构造思路
0654. 最大二叉树	每次找当前数组最大值为根节点	分治递归
0617. 合并二叉树	同步遍历两个树并合并节点	前序递归 / 层序队列

构造树结构的题目，不论是否显式要求使用“前序遍历”，其核心总是：先构造当前节点，再构造左右子树。

最近公共祖先（LCA）

题目	解法思路
0236. 二叉树的最近公共祖先	后序 + 回溯返回包含目标节点的子树
0235. BST 的最近公共祖先	根据有序性判断节点在哪一侧

二叉搜索树（BST）的性质问题

搜索 / 验证 / 转换类题目

题目	解法思路
0700. 二叉搜索树中的搜索	利用有序性，向左/右递归查找
0098. 验证二叉搜索树	中序遍历验证是否递增
0530. 最小绝对差	中序 + 前驱节点保存
0501. 二叉搜索树中的众数	中序统计频率，更新众数集合，适时清空结果集
0538. 把 BST 转换为累加树	反中序遍历 + 累加和

所有利用 BST 有序特性的问题（如最小差值、验证递增、累加转换）几乎都可通过中序遍历实现。 BST 中序遍历 = 有序数组。

BST 的修改与构造

题目	解法思路
0701. 插入操作	按序插入位置，递归返回新子树
0450. 删除操作	删除时分三种情况处理子节点
0669. 修剪 BST	递归返回修剪后的左右子树
0108. 有序数组转 BST	数组中点为根，递归构造

遍历选择指南

问题类型	推荐遍历顺序	选择理由
构造类 构造树结构	前序	当前节点必须先于子节点创建
求属性 深度、平衡、节点数	后序	需等左右子树返回值才能得出结果
路径类 路径总和、所有路径	前序 + 回溯	路径需在递归中积累，并在回溯中清除
搜索树（BST） 有序性题目	中序	利用中序遍历的有序性特征