主要概念：

  • 二叉树
  • 完全二叉树
  • 满二叉树
  • 完全平衡的二叉搜索树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
  • 二叉搜索树
  • 前缀树
    • 应用：
      • 搜索
      • 拼写检查
      • 输入预测
  • 线段树

遍历树的方法:

  • dfs（递归，分自上而下，自下而上）:
    • 前序
    • 中序
    • 后序
  • bfs（迭代)

TIPS:

  • 二叉搜索树的中序遍历是一个升序序列
  • 前、中、后序遍历均不能唯一确定一棵二叉搜索树，中序+后序、中序+先序可以唯一确定一棵二叉树
  • 前中后序的关系：inorder = sorted(postorder) = sorted(preorder)

高频题目：

96. 不同的二叉搜索树
解法：

  • 动态规划
  • 卡特兰数

98. 验证二叉搜索树
解法

  • 利用二叉搜索树的特点，递归
  • 利用二叉搜索树的特点和中序遍历，比较遍历得到的数组

101. 对称二叉树
解法：

  • 遍历比较
  • 迭代比较（队列）

104. 二叉树的最大深度
解法：

  • dfs解法
  • 迭代（栈）

108. 将有序数组转换为二叉搜索树

需要知道前中后序遍历各自的特点

解法：

  • 中序遍历创建

110. 平衡二叉树链接
解法：

  • 递归（自上而下，依据：有每个节点左右子树高度差不大于 1 时，该树才是平衡的）
  • 推荐自下而上的递归（后序遍历的应用），这样每个子节点只需要比较一次

111. 二叉树的最小深度
解法：

  • 递归，dfs
  • 迭代，dfs
  • 推荐，不需要遍历所有节点迭代，bfs

124.二叉树中的最大路径和
解法：

  • 递归不懂

173. 二叉搜索树迭代器
解法：

  • 中序遍历=》数组=》实现next(),hasNext()

208. 实现 Trie (前缀树)
解法：

  • 不会。。

226. 翻转二叉树
解法：

  • 递归
  • 迭代

235. 二叉搜索树的最近公共祖先
解法（利用二叉搜索树的特点）：

  • 递归
  • 迭代

236. 二叉树的最近公共祖先
解法：

  • 递归（主要想清楚边距条件）
  • 推荐存储父节点（map+set）

257. 二叉树的所有路径
解法：

  • 递归
  • 迭代

261 充钱
270 充钱
297.二叉树的序列化与反序列化
tips：

  • 序列化与反序列化
  • 递归

298 充钱
314 充钱