二叉树总结（hot100）
- 二叉树的中序遍历
- 思路1：递归法 - 按照 左->根->右 的顺序遍历
- 思路2：迭代法 - 使用栈，先将所有左节点入栈，出栈时处理，再处理右子树
- 二叉树的最大深度
- 思路：递归求解，返回左右子树的最大深度 + 1
- 特殊情况：空树返回0
- 翻转二叉树
- 思路：递归交换每个节点的左右子树
- 从上到下，每层都交换左右节点位置
- 对称二叉树
- 思路：递归比较左右子树是否对称
- 两个节点要对称必须: 值相等，左树的左=右树的右，左树的右=右树的左
- 二叉树的直径
- 思路：后序遍历，计算每个节点的左右子树深度之和
- 维护全局最大值，每个节点都计算经过它的最长路径
- 二叉树的层序遍历
- 思路：使用队列，先进先出
- 按层处理，每次处理一层的所有节点
- 需要记录每层的节点数
- 将有序数组转换为二叉搜索树
- 思路：选择数组中间位置作为根节点
- 递归构建左右子树
- 保持平衡的关键是每次选择中间位置
- 验证二叉搜索树
- 思路1：中序遍历，检查是否严格递增
- 思路2：递归时传入合法范围，检查每个节点是否在范围内
- 二叉搜索树中第K小的元素
- 思路：中序遍历到第k个元素即可
- 使用计数器记录当前是第几个元素
- 二叉树的右视图
- 思路：层序遍历，取每层最右边的节点
- 或使用深度优先搜索，优先访问右子树
- 二叉树展开为链表
- 思路：前序遍历存储节点
- 重新连接节点，全部作为右子节点
- 从前序与中序遍历序列构造二叉树
- 思路：前序确定根节点，中序确定左右子树范围
- 递归构建左右子树
- 使用哈希表优化中序遍历位置查找
- 路径总和III
- 思路：双重递归
- 以每个节点为起点都搜索一次
- 使用前缀和优化
- 二叉树的最近公共祖先
- 思路：后序遍历，因为要返回节点，先查找左右两棵树所以得查找完两棵树后才返回，是后续，此外两个节点不可能是一个节点所以，找到了返回节点就行
- 如果找到p或q，返回该节点
- 左右子树都返回非空，则当前节点为公共祖先
- 二叉树中的最大路径和
- 思路：后序遍历
- 维护全局最大值
- 计算经过每个节点的最大路径和
- 注意负值的处理
主要使用的解题技巧包括：
- 递归与迭代的灵活运用
- 合理使用辅助数据结构（栈、队列、哈希表）
- 理解并利用二叉树的特性（中序遍历有序、平衡性质等）
- 掌握常用遍历方式（前序、中序、后序、层序）