- 理解二叉树的遍历
- 从栈的“消除”到单调栈
- 回溯与剪枝: 《明日边缘》or 《源代码》
- Flood fill 算法小专题
- 二分搜索（待填坑）
- 排序: 经典排序算法的思想随处可见
- 与 Top-K 相关的问题
- 双指针与滑动窗口
- Trie 的原理、实现及其应用
- 线段树的构建、查询与更新
| 方法 | 注意点 | 能够解决的问题 |
|---|---|---|
| 前序遍历 | 将根节点的信息传递至左右子树 | 验证 BST: 98. Validate Binary Search Tree 判断两棵树是否完全相同: 100. Same Tree 判断是否为子树: 572. Subtree of Another Tree 根节点到叶子节点的路径问题: 113. Path Sum II 所有二叉树的构造问题都是前序遍历: 108. Convert Sorted Array to Binary Search Tree |
| 中序遍历 | BST 的中序遍历结果有序 | 验证 BST: 98. Validate Binary Search Tree BST 中第 K 小/大的元素: 230. Kth Smallest Element in a BST |
| 后序遍历 | 将左右子树的信息传回给根节点 | 二叉树的最大高度: 104. Maximum Depth of Binary Tree 二叉树的最小高度: 111. Minimum Depth of Binary Tree 翻转二叉树: 226. Invert Binary Tree 翻转二叉树为链表: 114. Flatten Binary Tree to Linked List 最近公共祖先问题: 236. Lowest Common Ancestor of a Binary Tree DP + BinaryTree: 337. House Robber III |
| 层序遍历 | 使用 queue 保存每一层的节点 BFS 用于求解无权图最短路径 |
寻找二叉树每一行的最大节点值: 515. Find Largest Value in Each Tree Row 二叉树的右视图: 199. Binary Tree Right Side View 多叉树最短路径问题: 310. Minimum Height Trees 二叉树中所有距离为 K 的节点: 863. All Nodes Distance K in Binary Tree |
| 方式 | 注意点 | 能够解决的问题 | 备注 |
|---|---|---|---|
| 对撞指针 | left 能否等于 right? |
二分搜索: 704. Binary Search 盛水最多的容器: 11. Container With Most Water N-Sum 问题: 15. 3Sum、18. 4Sum |
N-Sum 问题注意元素重复问题 |
| 快慢指针 | 寻找链表的中间节点: 876. Middle of the Linked List 判断链表是否有环: 141. Linked List Cycle 链表的归并排序: 148. Sort List |
||
| 滑动窗口 | 判断是否具有单调性质 | 最长无重复子串: 3. Longest Substring Without Repeating Characters 替换后的最长重复字符: 424. Longest Repeating Character Replacement 至多包含两个不同字符的最长子串: 159. Longest Substring with At Most Two Distinct Characters 乘积小于K的子数组: 713. Subarray Product Less Than K 最小覆盖子串: 76. Minimum Window Substring |
  |
