1. Trie树

2. 并查集

3. 高级搜索

  • 减枝、双向BFS、启发式搜索（A*）

    3.1 初级搜索

  1. 朴素搜索
  2. 优化方式： 不重复（fibonacci）、剪枝（生成括号问题）
  3. 搜索方向：
    1. DFS：
    2. BFS：

双向搜索、启发式搜索。

3.2 剪枝

  1. 爬楼梯 70

  2. 凑零钱（coin-change）

  3. 括号生成问题 22

  4. n皇后问题 （n-queens）

  5. 有效的数独 36

  6. 解数独 37

3.3 双向BFS

  1. 单词接龙 word-ladder 127

// BFS
// DFS
// Two-ended BFS

  1. 单词接龙 word-ladder-ii 126
  1. 最小基因变化 433

3.4 启发式搜索 Heuristic Search（A*）

———基于BFS

  • 基本思想是使用优先队列替换普通队列，然后定优先级。（优先级函数）
  1. 二进制矩阵中的最短路径 1091

  1. 滑动谜题 773

    // DFS
    // BFS
    // A*

  1. 解数独 37

4. 高级树&AVL&红黑树

4.1 高技 树

4.2 AVL

  • 左右子树高度差<=1
  • 节点需要存储额外的信息(平衡因子)，且调整次数频繁

4.3 红黑树

  • 近似平衡的二叉搜索树，能确保左右子树的高度差小雨两倍
  • 要求：
    • 每个节点要么是红色、要么是黑色
    • 梗节点是黑色
    • 每个叶子结点（Nil 或者空 ）节点是黑色
    • 相邻节点不能为红
    • 从任意一个节点到叶子结点的路径都包含相同数目的黑色节点

4.4