二叉树专题

二叉树是一种重要的非线性数据结构，每个节点最多有两个子节点。二叉树是许多高级数据结构的基础，也是算法面试中的重点内容。本专题整理了二叉树相关的经典算法题及其解法。

目录

基础理论

• 理论基础
• 二叉树总结

遍历方法

• 递归遍历
• 迭代遍历
• 统一迭代
• 层序遍历

二叉树属性

• 对称二叉树
• 最大深度
• 最小深度
• 完全二叉树节点个数
• 平衡二叉树
• 所有路径
• 左叶子之和
• 左下角的值
• 路径总和

二叉树修改与构造

• 翻转二叉树
• 从中序遍历和后序遍历构造二叉树
• 最大二叉树
• 合并二叉树

二叉搜索树

• 二叉搜索树中的搜索
• 验证二叉搜索树
• 二叉搜索树的最小绝对差
• 二叉搜索树中的众数
• 二叉搜索树中的插入
• 二叉搜索树的删除
• 二叉搜索树的修剪
• 将有序数组转换为二叉搜索树
• 二叉搜索树转换为累加树

公共祖先问题

• 二叉树的最近公共祖先
• 二叉搜索树的最近公共祖先

学习要点

• 二叉树的基本概念：节点、根、叶子、深度、高度
• 二叉树的存储方式：链式存储、数组存储
• 二叉树的遍历：前序、中序、后序、层序
• 递归与迭代的实现方式
• 二叉搜索树的性质与应用
• 平衡二叉树的概念
• 完全二叉树的特性

核心思想

• 递归思想：二叉树的很多问题都可以通过递归来解决
• 分治思想：将大问题分解为子问题
• 深度优先搜索（DFS）：前序、中序、后序遍历
• 广度优先搜索（BFS）：层序遍历
• 二叉搜索树性质：中序遍历得到有序序列