二叉树

树题是刷题修行的主线任务之一。本合集按套路分节收录二叉树题目：每题给出关键观察、做法与复杂度。

二叉搜索树

BST 的第一反应是中序遍历——中序遍历 BST 会得到一个严格递增的序列，大量题目围绕这条性质展开。

leetcode 2476

中序遍历得到递增序列，对每个询问在序列上做一次二分查找。中序遍历 $O(n)$，每个询问 $O(\log n)$，记询问数为 q，整体 $O(n + q \log n)$。

leetcode 1932

合并 BST。需要先观察出两条性质：

1. 根节点是唯一的。 能成为最终根的树，其根值没有出现在任何叶子上，也就无法「被」合并；如果这样的树不止一棵...

Read more

一文解决逆序数

数组里满足 i < j 且 a[i] > a[j] 的一对下标叫一个逆序对，逆序数就是这种对的总数。一道逆序数，四种写法，从面试到竞赛一网打尽。计算逆序数有两种思路：

1. 归并排序：合并左右两个已排好序的半段时，每当右半段的元素先出列，答案就加上左半段还没出列的元素个数（面试版代码里的 n - p1）。两边相等时让左边先出列，所以比较用严格的 >：写成 >= 会把相等的数也算成逆序，[2,2,2,2] 会得到 6 而不是 0；
2. 值域计数：先把值离散化成名次 rank（值在去重排序后的位置，取 1 到 m，m 是不同值的个数），从左往右逐个把元素 rank 位置的计数加一；当...

Read more