高频面试题

LCR 174 https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二叉搜索树前序遍历为递增序列，而把前序遍历反过来可以得到递减序列。 如何把前序遍历反过来呢？为 “右、根、左” 顺序。 当访问到第 cnt 个节点，即可返回。 时间复杂度：O(n) 空间复杂度：O(n) ...

LCR 159 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 快速选择算法，可以使数组 [0, k] 有序。 时间复杂度：O(n) 空间复杂度：O(logn) ...

LeetCode 440 https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 题解参考灵神（https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/3696254/zai-shi-cha-shu-shang-zhao-di-k-xiao-olo-vzkl/）。 本题可以看成一颗十叉树。 先序遍历这棵树，等价于从左到右遍历字典序列表。所以先序遍历访问到的第 k 个节点就是答案。 每访问一个节点，就把 k 减一。当 k=0 时，当前节点就是答案。 从根节点的第一个儿子 1 开始。由于该节点被我们访问了，先把 k 减一。 设子树 1 的大小（节点个数）为 size。分类讨论： 如果 size≤k，那么答案不在子树 1 中。然后考虑下一个儿子 2，依此类推。访问到下一个儿子时，要把 k 减去 (size−1)+1=size，这里 size−1 是因为节点 1 已经访问过了。 否则，答案在子树 1 中。首先访问 1 的儿子 10，把 k 减一。依次考虑 1 的儿子 10,11,12,…,19，计算子树大小，比较子树大小与 k 的大小关系，依此类推。 问：为什么判断条件是 size≤k 而不是 size<k？ 答：因为当我们访问到子树根节点时，就把 k 减一了。这时再算子树大小，就把根节点重复统计了，所以是 size−1<k，即 size≤k。 如何计算子树大小 子树每层的节点个数是有规律的，可以逐层统计。 比如 n = 1234，计算子树 1 的大小： 第一层，只有 1 一个节点。 第二层，最小是 10，最大是 19，有 10 个节点。 第三层，最小是 100，最大是 199，有 100 个节点。 第四层，最小是 1000，最大是 n=1234，有 n−1000+1=235 个节点。 所以一共有 1+10+100+235=346 个节点。 上述过程如何用代码实现？ 每一层的最小值是好算的：1→10→100→1000。 最大值呢？看上去不太好算。 不妨改为 2→20→200→min(2000,n+1)，这个过程中的每个数减一，就是每一层的最大值。 时间复杂度：\(O(Dlog^2n)\)，其中 D=10。整棵树有 O(logn) 层，每层会遍历至多 D 个节点，每个节点需要 O(logn) 的时间计算子树大小。 空间复杂度：O(1)。 ...

LeetCode 572 https://leetcode.cn/problems/subtree-of-another-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 如果暴力匹配，时间复杂度是 O(n⋅min(n,m))，如何改进呢？ 定义节点 node 的高度为 node 到其最深叶子的路径上的节点个数。特别地，叶子的高度为 1。设 subRoot 的高度为 hs。 设 node 为 root 中的节点。我们可以在匹配之前，先判断 node 的高度是否等于 hs，只有在相等时才做匹配。 这样做的时间复杂度是多少呢？ 首先，对于 root 中的两个高度相同的节点 p 和 q（p  =q），不可能出现 p 是 q 的祖先，或者 q 是 p 的祖先。因为如果 p 是 q 的祖先，那么 p 的高度必然大于 q 的高度，反之亦然。 其次，对于 root 中的两个高度相同的节点 p 和 q（p != q），子树 p 和子树 q 没有任何交集。假如有交集，说明从 p 出发可以到达某个点 node，从 q 出发也可以到达 node，但这只有在 p 是 q 的祖先，或者 q 是 p 的祖先时才成立，与两个节点高度相同矛盾。 所以，root 中的所有与 hs 高度相同的节点，对应的子树两两不相交，这些子树的节点个数之和不超过 n，所以总的匹配次数也不会超过 n，下面代码中的 dfs 的时间复杂度为 O(n)。 时间复杂度：O(n+m)，其中 n 是二叉树 root 的节点个数，m 是二叉树 subRoot 的节点个数。注意当 subRoot 的节点个数比 n 还要多时，dfs 并不会遍历 subRoot 中的所有节点。其中 O(m) 是计算 subRoot 树高的时间，如果限制 getHeight 递归访问的节点个数至多为 n，则可以做到 O(n) 的时间复杂度。 空间复杂度：O(n+m)。如果限制 getHeight 递归访问的节点个数至多为 n，则可以做到 O(n) 的（栈）空间复杂度。 ...

LeetCode 75 https://leetcode.cn/problems/sort-colors/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ O(1) 插入元素 不是插入元素，而是修改元素！ 维护 a 中 0 的个数，即改为 0 的位置，记作 p0。维护 a 中 0 和 1 的个数，即改为 1 的位置，记作 p1。 首先将 x 改为 2，如果 x <= 1，nums[p1++] = 1，如果 x == 0，nums[p0++] = 0。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 145 https://leetcode.cn/problems/binary-tree-postorder-traversal/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二叉树后序遍历。 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。 ...

LeetCode 50 https://leetcode.cn/problems/powx-n/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 快速幂。 时间复杂度：O(log∣n∣)。 空间复杂度：O(1)。 ...

LCR 143 https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 具有相同子结构的条件是： A、B 非空 dfs(A, B) 或 dfs(A->left, B) 或 dfs(A->right, B) 时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M)，每次调用 dfs(A, B) 判断占用 O(N)。 空间复杂度 O(M)： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M ≤ N 时，遍历树 A 与递归判断的总递归深度为 M；当 M > N 时，最差情况为遍历至树 A 的叶节点，此时总递归深度为 M。 ...

LeetCode 518 https://leetcode.cn/problems/coin-change-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 完全背包题目。 dfs(i, c) = dfs(i − 1, c) + dfs(i, c − coins[i]) 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。 空间复杂度：O(n⋅amount)。 ...

LeetCode 59 https://leetcode.cn/problems/spiral-matrix-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 初始化一个 n×n 的矩阵，一开始所有元素均为 0。 用一个长为 4 的方向数组 DIRS=[(0,1),(1,0),(0,−1),(−1,0)] 分别表示右下左上 4 个方向。同时用一个下标 di 表示当前方向，初始值为 0，表示一开始向右。 每次移动，相当于把行号增加 DIRS[di][0]，把列号增加 DIRS[di][1]。 向右转 90°，相当于把 di 增加 1，但在 di=3 时要回到 di=0。两种情况合二为一，把 di 更新为 (di+1)mod4。 时间复杂度：\(O(n^2)\)。 空间复杂度：O(1)。返回值不计入。 ...