堆

第k大/小

leetcode 373
如果说要枚举所有点对，复杂度至少是O(n^2)起步。
想办法利用非递减顺序排列的性质：想象一个矩阵，纵坐标表示nums1下标，横坐标表示nums2下标，矩阵的值是数对和，这样一个矩阵有什么性质？显然每行都是非递减序列，每列也都是非递减序列，左上角(0, 0)点对和最小。
这样维护一个最小堆，先把第一列入堆，然后开始出堆，出堆元素坐标(i, j)，每出堆一个元素对应入堆一个元素，入堆元素坐标有两个选择：(i + 1, j)和(i, j + 1)。由于开始先把第一列入堆，所以取(i + 1, j)位置会导致重复入堆，只加(i, j + 1)即可，注意j +

Read more

二叉树

二叉搜索树

特点：一般用中序遍历 性质：中序遍历会得到一个单调递增的序列
leetcode 2476
中序遍历得到递增序列，对于每个询问做一次二分查找，时间复杂度O(n*logn)

最近公共祖先

leetcode 236
普通二叉树LCA，用分类讨论的方式思考：
1、遍历到空节点，返回节点本身（root）
2、遍历到p、q，不需要继续遍历，另一个节点要么在它子树中，要么在它祖先的另一侧，这两种情况都返回节点本身（root）
3、p、q在左右子树，返回当前节点（root）
4、p、q在左子树，返回左子树（root.left）
5、p、q在右子树，返回右子树（root.right）
6

Read more