Jack N @ GitHub

Full stack AI Engineer, focus on: React, Next.js, node.js and .Net

1. 题目

给定一个链表头节点 head,判断链表中是否存在环。若存在环返回 true,否则返回 false。

进阶:你能用 O(1)(即常量)内存解决此问题吗?

示例:

1
2
3
4
5
6
7
8
输入: head = [3, 2, 0, -4],且尾节点连回索引 1 的节点
输出: true(存在环)

输入: head = [1, 2],2 -> 1 成环
输出: true

输入: head = [1],无环
输出: false

节点定义:

1
2
3
4
5
6
7
8
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val ?? 0;
this.next = next ?? null;
}
}

2. 解题思路

2.1 哈希集合(直观)

遍历链表,把访问过的节点存进 Set。若再次遇到已在集合里的节点,说明成环。

  • 时间 O(n),空间 O(n)。缺点:不满足「常量内存」。

2.2 快慢指针(Floyd 判圈,最优)

想象跑道:快的和慢的在一个环形跑道上一定会相遇。

  • slow 每次走 1 步,fast 每次走 2 步,都从 head 出发。

  • 若有环,fast 最终会从后面追上 slow,两者相遇 → 返回 true。

  • 若无环,fast(或 fast.next)会先到 null → 返回 false。

  • 时间复杂度:O(n)。

  • 空间复杂度:O(1),只用两个指针。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function hasCycle(head: ListNode | null): boolean {
let slow = head;
let fast = head;

while (fast !== null && fast.next !== null) {
slow = slow!.next; // 走一步
fast = fast.next.next; // 走两步

if (slow === fast) return true; // 相遇即有环
}

return false; // fast 到头,无环
}

// 测试:构造 3 -> 2 -> 0 -> -4 -> (回到 2)
const n = new ListNode(3, new ListNode(2, new ListNode(0, new ListNode(-4))));
n.next.next.next.next = n.next; // 造环
console.log(hasCycle(n)); // true
console.log(hasCycle(new ListNode(1))); // false

4. 面试延伸

  • 为什么快指针不能走 3 步? 走 2 步能保证追上;步长差为 1 时相遇最有保证,是经典设定。
  • 求环入口节点 是本题的孪生题(LeetCode 142),见下一篇 [寻找环形链表入口节点]。
  • 快慢指针的通用套路还能解:链表中点、判断回文链表、数组找重复数(287) 等「成环」问题。
  • 边界:fast && fast.next 的判空顺序不能反,否则访问 fast.next.next 会空指针。

难度:简单 | LeetCode 141 题 | 快慢指针代表作

1. 题目

实现一个函数 promiseAll(iterables),行为对齐原生 Promise.all:

  • 接收一个(Promise 或普通值可迭代)数组,返回一个新 Promise。
  • 全部成功时,新 Promise 以「与输入顺序一致」的结果数组 resolve。
  • 任意一个失败时,立即 reject 第一个失败的原因(快速失败)。
  • 要能处理非 Promise 元素(普通值直接当作已成功)。
  • 空数组应立即 resolve 为 []。

示例:

1
2
3
4
5
promiseAll([1, Promise.resolve(2), fetchUrl])
-> resolve 为 [1, 2, <fetch结果>](顺序保持)

promiseAll([ok1, fail, ok2])
-> reject(fail 的原因)

2. 解题思路

三个关键点:

  1. 顺序保持:结果数组按输入下标写入,不能用 push(谁先完成谁 push 会乱序)。给每个任务捕获其 index,完成时 results[index] = value。
  2. 完成计数:用一个计数器 completed,每当一个任务成功就 +1;当 completed === 总长度 时 resolve(results)。因为异步完成顺序不定,只能靠计数判断「全好了」。
  3. 快速失败:在任一任务 catch 到错误时,直接 reject(reason)。Promise 一旦 settle 就冻结,后续再 reject 无效,所以无需额外加锁,天然只 reject 第一次。

用 Promise.resolve(x).then(...) 包裹每个元素,可同时兼容「普通值」和「Promise」——普通值会被包装成已完成的 Promise。

  • 时间复杂度:O(n)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function promiseAll<T>(
iterables: Iterable<T | PromiseLike<T>>
): Promise<Awaited<T>[]> {
return new Promise((resolve, reject) => {
const promises = Array.from(iterables);
const n = promises.length;
const results = new Array(n);
let completed = 0;

if (n === 0) {
resolve(results as Awaited<T>[]);
return;
}

for (let i = 0; i < n; i++) {
// 用 Promise.resolve 兼容非 Promise 值
Promise.resolve(promises[i]).then(
(value) => {
results[i] = value; // 按下标写入,保证顺序
completed++;
if (completed === n) {
resolve(results as Awaited<T>[]);
}
},
(reason) => {
reject(reason); // 快速失败
}
);
}
});
}

// 测试
promiseAll([1, Promise.resolve(2), new Promise((r) => setTimeout(() => r(3), 100))])
.then(console.log); // [1, 2, 3]

promiseAll([Promise.resolve("a"), Promise.reject("boom"), Promise.resolve("c")])
.catch(console.log); // "boom"

4. 面试延伸

手写 Promise 家族常一起问,趁热记住区别:

  • Promise.allSettled:等全部 settle(不管成败),返回 {status, value/reason} 数组,永不 reject。
  • Promise.race:第一个 settle(含 reject)的结果定胜负。
  • Promise.any:第一个成功的结果;全部失败才 reject 一个 AggregateError。
  • 并发控制(重点):真实场景不能无脑并发几千个请求。进阶手写 promiseAllLimit(tasks, limit),用「任务池 / 索引指针」维持最多 limit 个在跑,是字节/腾讯高频加试题。
  • 别忘了答「为什么按 index 写而不是 push」——这几乎是本题的核心得分点。

难度:中等 | 前端手写 Promise 必考 | 异步并发基石

1. 题目

实现一个节流函数 throttle(fn, wait):

  • 事件被频繁触发时,每 wait 毫秒最多执行一次 fn。
  • 与防抖不同:节流不要求「安静下来」,而是给执行限速,保证一段时间内至少/至多按节奏跑。
  • 保留正确的 this 与参数。

典型场景:滚动加载、拖拽、游戏连续射击、鼠标 mousemove 计算、大屏 resize。

示例:

1
2
滚动页面每 5ms 触发一次 scroll
throttle(onScroll, 200) -> 每 200ms 才真正执行一次

2. 解题思路

节流有两种主流实现,各自优缺点分明,面试最好都会写。

2.1 时间戳版(保证间隔,可能丢失最后一次)

记录上次执行时间 last。每次触发比较 now - last >= wait:满足就执行并更新 last;否则这次丢弃。

  • 优点:首次触发立即执行(leading)。
  • 缺点:如果最后一次触发落在间隔内,会被丢弃,即「尾巴」不执行(trailing 缺失)。

2.2 定时器版(保证最后一次会执行)

用 timer 作为「是否处于执行中」的锁。触发时若空闲,延迟 wait 后执行并上锁;执行完释放锁。这样停手后仍会把最后一次补执行一次。

  • 优点:保证 trailing 执行。
  • 缺点:首次不是立即执行,而是延迟 wait。

2.3 结合版(leading + trailing)

时间戳 + 定时器合体:既保证首次立即执行,又保证最后一次停止触发后一定收尾。这是 lodash 的行为。

  • 时间复杂度:每次触发 O(1)。

3. TypeScript 实现

3.1 时间戳版

1
2
3
4
5
6
7
8
9
10
11
12
13
function throttleTimestamp<T extends (...args: any[]) => void>(
fn: T,
wait: number
) {
let last = 0;
return function (this: any, ...args: Parameters<T>) {
const now = Date.now();
if (now - last >= wait) {
last = now;
fn.apply(this, args);
}
};
}

3.2 定时器版

1
2
3
4
5
6
7
8
9
10
11
12
13
function throttleTimer<T extends (...args: any[]) => void>(
fn: T,
wait: number
) {
let timer: ReturnType<typeof setTimeout> | null = null;
return function (this: any, ...args: Parameters<T>) {
if (timer !== null) return; // 执行中,丢弃
timer = setTimeout(() => {
timer = null;
fn.apply(this, args);
}, wait);
};
}

3.3 结合版(leading + trailing,推荐)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function throttle<T extends (...args: any[]) => void>(fn: T, wait: number) {
let timer: ReturnType<typeof setTimeout> | null = null;
let last = 0;

return function (this: any, ...args: Parameters<T>) {
const now = Date.now();
const remaining = wait - (now - last);

if (remaining <= 0) {
// 到点了:立即执行
if (timer !== null) {
clearTimeout(timer);
timer = null;
}
last = now;
fn.apply(this, args);
} else if (timer === null) {
// 没到点且没有排队:挂一个定时器保证最后一次执行
timer = setTimeout(() => {
last = Date.now();
timer = null;
fn.apply(this, args);
}, remaining);
}
};
}

// 用法
const onScroll = throttle(() => console.log("handle scroll"), 200);
window.addEventListener("scroll", onScroll);

4. 面试延伸

  • 节流 vs 防抖 一句话:节流是「匀速放行」,防抖是「攒一波再放」;打字联想用防抖,滚动/射击用节流。
  • requestAnimationFrame 节流:滚动/resize 类视觉更新用 rAF 对齐浏览器帧率比 setTimeout 更流畅省电。
  • passive: true:给 scroll/touch 监听加被动选项,配合节流进一步消除卡顿,全栈性能考点。
  • lodash throttle 本质就是 debounce(fn, wait, { leading: true, trailing: true }) 的特例,理解这层关系能秒杀追问。

难度:中等 | 前端手写题必考 | 性能优化基本功

1. 题目

实现一个防抖函数 debounce(fn, wait, immediate):

  • 在事件被频繁触发时,只有在停止触发 wait 毫秒后,fn 才真正执行一次。
  • 每次新触发都会「重新计时」(把上一次的待执行取消)。
  • immediate = true 时,首次触发立即执行一次,之后的连续触发不再执行,直到静默 wait 后重新武装。
  • 要求保留正确的 this 与参数,并提供 cancel 方法取消待执行。

典型场景:搜索框输入联想、窗口 resize 重排、按钮防连点、滚动监听。

示例:

1
2
用户连续输入 "typescript"(每 50ms 一个字符)
debounce(search, 300) -> 停止输入 300ms 后才发一次请求

2. 解题思路

一句话:用一个闭包持有的定时器 ID,每次触发先 clearTimeout 再重新 setTimeout。这样只有「最后一次触发」的定时器能活到时间并执行回调。

要点:

  1. timer 存在闭包里,外界看不见,只在函数内部读写。
  2. 执行回调时用 fn.apply(this, args),保证 this 指向调用方(比如事件绑定的 DOM),参数也原样透传。
  3. immediate 版本:若已立即执行过,就把 timer 设为一个哨兵值表示「冷却中」,静默期结束后置空以重新武装。
  4. cancel:清掉当前定时器并把状态复位。
  • 时间复杂度:每次触发 O(1)。
  • 空间:闭包一份。

3. TypeScript 实现

3.1 标准版(延迟执行,最常用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function debounce<T extends (...args: any[]) => void>(
fn: T,
wait: number
): ((...args: Parameters<T>) => void) & { cancel: () => void } {
let timer: ReturnType<typeof setTimeout> | null = null;

const debounced = function (this: ThisParameterType<T>, ...args: Parameters<T>) {
if (timer !== null) clearTimeout(timer);
timer = setTimeout(() => {
timer = null;
fn.apply(this, args);
}, wait);
};

debounced.cancel = () => {
if (timer !== null) {
clearTimeout(timer);
timer = null;
}
};

return debounced;
}

3.2 支持 immediate(首次立即执行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function debounceImmediate<T extends (...args: any[]) => void>(
fn: T,
wait: number,
immediate = false
) {
let timer: ReturnType<typeof setTimeout> | null = null;

return function (this: any, ...args: Parameters<T>) {
// 用 timer 是否存在判断「是否处于冷却」
if (timer !== null) clearTimeout(timer);

if (immediate) {
const callNow = timer === null; // 首次或冷却结束
timer = setTimeout(() => {
timer = null; // 重新武装
}, wait);
if (callNow) fn.apply(this, args);
} else {
timer = setTimeout(() => {
timer = null;
fn.apply(this, args);
}, wait);
}
};
}

// 用法
const onSearch = debounce((kw: string) => console.log("fetch:", kw), 300);
window.addEventListener("input", () => onSearch("abc"));
// 组件卸载 / 不再需要时:
onSearch.cancel();

4. 面试延伸

  • 防抖 vs 节流:防抖「等安静了再执行一次」,节流「固定频率最多执行一次」。二者常一起考,见下一篇 [节流]。
  • 带返回值怎么办? 防抖天然会推迟结果,直接 return 拿不到。工程做法:返回 Promise,或用回调;能讲清这个取舍很加分。
  • leading / trailing 配置:lodash 的 debounce 有 leading(是否先行执行)、maxWait(最长等待,防止永远不执行,此时退化为带节流的防抖)。
  • React 中要配合 useMemo/useRef 保存同一个 debounce 实例,否则每次渲染都新建、定时器互相打架。

难度:简单 | 前端手写题必考 | 事件频率控制基石

1. 题目

实现一个函数,把可能嵌套多维的数组「摊平」成一维数组。前端面试手写题常客。

示例:

1
2
flatten([1, [2, [3, [4]], 5]])  ->  [1, 2, 3, 4, 5]
flatten([1, [2, 3], 4]) -> [1, 2, 3, 4]

进阶要求:支持指定「扁平化深度」 flatten(arr, depth),depth 表示要展开几层,Infinity 表示全部展开(对齐 Array.prototype.flat 的行为)。

2. 解题思路

嵌套结构 = 天然的递归场景。核心逻辑一句话:

遍历数组,遇到元素是数组就递归展开并把结果拼接,否则直接收集。

对于「限深度」版本,给递归加一个 depth 参数,每下钻一层 depth - 1,为 0 时不再展开直接返回当前层拷贝。

可以用多种流派展示功力:

  • reduce + 递归(最能体现思路,面试首推)。

  • 展开运算符 + 递归。

  • while + some + concat(检测是否还有数组,逐步拉平)。

  • toString 的副作用 trick(不推荐,会把 null 变空串)。

  • 生成器 function*(工程优雅,可迭代惰性展开)。

  • 时间复杂度:O(N),N 为所有层级元素总数。

  • 空间复杂度:O(N) + 递归栈 O(最大深度)。

3. TypeScript 实现

3.1 基础版:reduce + 递归

1
2
3
4
5
6
7
8
9
type Nested = number | Nested[];

function flatten(arr: Nested[]): number[] {
return arr.reduce<number[]>(
(acc, cur) =>
acc.concat(Array.isArray(cur) ? flatten(cur) : cur),
[]
);
}

3.2 进阶版:支持 depth(对齐 Array.flat)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function flattenDepth(arr: Nested[], depth = 1): number[] {
const res: number[] = [];

const dfs = (input: Nested[], d: number) => {
for (const item of input) {
if (Array.isArray(item) && d > 0) {
dfs(item, d - 1); // 下钻一层,深度预算 -1
} else {
res.push(item as number);
}
}
};

dfs(arr, depth);
return res;
}

3.3 生成器版:可迭代、优雅

1
2
3
4
5
6
7
8
function* genFlat(arr: Nested[]): Generator<number> {
for (const item of arr) {
if (Array.isArray(item)) yield* genFlat(item);
else yield item;
}
}

const flattenGen = (arr: Nested[]): number[] => [...genFlat(arr)];
1
2
3
4
// 测试
console.log(flatten([1, [2, [3, [4]], 5]])); // [1,2,3,4,5]
console.log(flattenDepth([1, [2, [3]]], 1)); // [1,2,[3]] -> [1,2,3 保留]
console.log(flattenDepth([1, [2, [3, [4]]], 5], Infinity)); // [1,2,3,4,5]

4. 面试延伸

  • flat vs flatMap:flatMap 只展开一层且能 map,性能略优于 map().flat()。
  • 对象/字符串边界:真实项目要判 Array.isArray,别用 typeof === 'object',否则 null、字典对象会被误展开。
  • 保持类型:泛型进阶 type Flat<T> = ... 能在类型层面推导扁平结果,展示 TS 功底。
  • 一句话:能默写递归版是底线,能顺手写出限深度 + 生成器版就是加分项。

难度:简单 | 前端手写题 Top 10 | 递归基本功

1. 题目

给定一个整数数组 nums,把它按升序排序。要求手写快速排序,并分析平均与最坏时间复杂度、空间复杂度。

示例:

1
2
输入: [5, 2, 9, 1, 5, 6]
输出: [1, 2, 5, 5, 6, 9]

2. 解题思路

快速排序基于分治(Divide & Conquer):

  1. 选基准 pivot:从数组里挑一个值(首/尾/随机/三数取中)。
  2. 分区 partition:重排数组,使「小于 pivot 的在左边、大于的在右边」,并把 pivot 放到它最终应在的位置 p。
  3. 递归:对左右两个子区间分别快排。

分区是灵魂。最常用 Lomuto 方案:以最后一个元素为 pivot,用指针 i 维护「小于区」的右边界,遍历指针 j,遇到比 pivot 小的就与 i+1 交换。

复杂度:

  • 平均时间 O(n log n),每次大致对半分。
  • 最坏时间 O(n²):数组已有序且总选端点为 pivot,退化为链式划分。随机化 pivot 可高概率避免。
  • 空间 O(log n):递归栈(原地版本),非原地拼接版本为 O(n)。
  • 快排是不稳定排序(相等元素相对顺序可能改变)。

3. TypeScript 实现

3.1 简洁版(易记,额外空间 O(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSortSimple(nums: number[]): number[] {
if (nums.length <= 1) return nums;

const pivot = nums[Math.floor(nums.length / 2)];
const left: number[] = [];
const mid: number[] = [];
const right: number[] = [];

for (const x of nums) {
if (x < pivot) left.push(x);
else if (x === pivot) mid.push(x);
else right.push(x);
}

return [...quickSortSimple(left), ...mid, ...quickSortSimple(right)];
}

用 mid 单独收集等于 pivot 的元素,能正确处理重复值且不重复比较,避免部分实现卡在相等上。

3.2 原地版(面试官更想看的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function quickSort(nums: number[], lo = 0, hi = nums.length - 1): number[] {
if (lo >= hi) return nums;

const p = partition(nums, lo, hi);
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
return nums;
}

function partition(nums: number[], lo: number, hi: number): number {
// 随机化 pivot,避免有序数据退化
const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
[nums[rand], nums[hi]] = [nums[hi], nums[rand]];

const pivot = nums[hi];
let i = lo; // i 指向「小于区」的下一个位置

for (let j = lo; j < hi; j++) {
if (nums[j] < pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
}
}

[nums[i], nums[hi]] = [nums[hi], nums[i]]; // pivot 归位
return i;
}

// 测试
console.log(quickSort([5, 2, 9, 1, 5, 6])); // [1,2,5,5,6,9]

4. 面试延伸

  • 为什么快排实践中比归并快? 原地、缓存友好、常数小;归并需要额外数组。
  • ** nth element / Top-K(快速选择 215 题)**:partition 后只递归一边,平均 O(n) 找第 K 大,是快排的孪生应用。
  • 三路快排(Dutch National Flag):把区间分成 < == > 三段,专门治「大量重复元素」,此时等于段直接不再递归。
  • 手写必问:pivot 怎么选?最坏什么情况?是否稳定?——三点答上来就是满分。

难度:中等 | 手写排序基本功 | 快速选择衍生高频

1. 题目

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。

示例:

1
2
3
4
5
6
7
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: [1,3] 与 [2,6] 重叠,合并为 [1,6]

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 端点相接也算重叠

2. 解题思路

区间能否合并,取决于它们在数轴上的相对位置。若无序,两个区间可能隔着十万八千里却要判重,非常麻烦。核心思路:先按左端点排序,让可能重叠的区间彼此相邻,然后一次线性扫描。

排序后遍历,维护结果数组 res,对当前区间 cur:

  1. 若 res 为空,或 cur.start > res 最后一个.end(不重叠)→ 直接 push 新区间。
  2. 否则说明重叠 → 合并:更新最后一个区间的 end = max(旧end, cur.end)。

为什么是 max?考虑 [[1,10],[2,3]],第二个区间完全被包含,end 不能取 cur.end,要保留较大的那个。

  • 时间复杂度:O(n log n),排序主导。
  • 空间复杂度:O(n)(存结果;不计则为 O(log n) 排序栈)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function merge(intervals: number[][]): number[][] {
if (intervals.length === 0) return [];

// 按左端点升序
intervals.sort((a, b) => a[0] - b[0]);

const res: number[][] = [];

for (const cur of intervals) {
const last = res[res.length - 1];

// 无结果 或 与上一个不重叠 -> 开新区间
if (!last || cur[0] > last[1]) {
res.push([...cur]);
} else {
// 重叠 -> 合并,取右端点较大者
last[1] = Math.max(last[1], cur[1]);
}
}

return res;
}

// 测试
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1,6],[8,10],[15,18]]
console.log(merge([[1, 4], [4, 5]])); // [[1,5]]
console.log(merge([[1, 10], [2, 3]])); // [[1,10]]

4. 面试延伸

  • 插入区间(57 题):找到插入位置,把与新区间相交的全部吞并,取新端点。
  • 区间相交 / 无重叠最少删除(435 题):按右端点排序 + 贪心,是另一条主线,别和本题的左端点排序搞混。
  • 会议室 II(253 题):求同时进行的最多区间数,用最小堆或「起点/终点分别排序 + 双指针扫描线」。
  • 通用套路:区间题先想排序策略(按左?按右?),再决定扫描时维护什么状态。

难度:中等 | LeetCode 56 题 | 排序 + 扫描线经典

1. 题目

给你二叉树的根节点 root,返回其节点值的层序遍历(逐层从左到右访问所有节点),结果按层分组。

示例:

1
2
3
4
5
6
7
8
        3
/ \
9 20
/ \
15 7

输入: root = [3, 9, 20, null, null, 15, 7]
输出: [[3], [9, 20], [15, 7]]

节点定义同前(TreeNode)。

2. 解题思路

层序遍历 = 广度优先搜索(BFS),天然对应队列(先进先出)。

难点在于「如何把结果按层分开」。关键技巧:

每轮 while 开始时,队列里的元素恰好就是「当前层的全部节点」,数量为 queue.length。用 for (let i = 0; i = levelSize) 固定处理这一层,处理时把下一层的孩子依次入队。

流程:

  1. 根节点入队。
  2. 当队列非空:取 levelSize = queue.length,循环 levelSize 次,每次出队一个节点记录其值,并把它的左右孩子入队。
  3. 一层结束后,把这层的值数组 push 进结果。
  • 时间复杂度:O(n)。
  • 空间复杂度:O(n),队列最多容纳一层的节点(完全二叉树最后一层约 n/2)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function levelOrder(root: TreeNode | null): number[][] {
if (root === null) return [];

const res: number[][] = [];
const queue: TreeNode[] = [root];

while (queue.length > 0) {
const levelSize = queue.length;
const level: number[] = [];

for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}

res.push(level);
}

return res;
}

性能提示:Array.shift() 是 O(n),节点很多时可改用索引指针 head 模拟队列头,或直接用两个数组交替,避免频繁移动。面试手写版本用 shift 完全 OK。

4. 面试延伸

  • 锯齿形层序遍历(103 题):偶数层反转 level,或双端队列两头取。
  • 自底向上层序(107 题):正常 BFS 最后 res.reverse()。
  • 右视图(199 题):每层只取最后一个节点值 level[levelSize - 1]。
  • 最小深度 / 最短路径类:BFS 求「层数」正是 [最大深度] 一文的 BFS 解法,也常用于网格最短步数。
  • 一句话记忆:BFS 用队列、DFS 用栈(或递归);「按层」是 BFS 的标志。

难度:中等 | LeetCode 102 题 | BFS 模板题

1. 题目

给定一个二叉树 root,返回其最大深度。

二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例:

1
2
3
4
5
6
7
8
9
10
11
        3
/ \
9 20
/ \
15 7

输入: root = [3, 9, 20, null, null, 15, 7]
输出: 3 (最长路径 3 -> 20 -> 15 或 3 -> 20 -> 7,共 3 个节点)

输入: root = []
输出: 0

节点定义:

1
2
3
4
5
6
7
8
9
10
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left ?? null;
this.right = right ?? null;
}
}

2. 解题思路

2.1 DFS 递归(最直观)

最大深度满足递归定义:

1
2
depth(node) = 1 + max(depth(node.left), depth(node.right))
depth(null) = 0

即:当前节点深度 = 左右子树更深的那个 + 1(加自己这一层)。这是典型的「把子问题答案直接组合」的递归。

  • 时间复杂度:O(n),每个节点访问一次。
  • 空间复杂度:O(h),递归栈,最坏 O(n)(退化成链表)。

2.2 BFS 层序

按层遍历,遍历到第几层,深度就是几。用队列 + for 循环固定「一层」的节点数,每处理完一层 depth++。适合顺带求最小深度、按层输出等变体。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// DFS 递归
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS 层序
function maxDepthBFS(root: TreeNode | null): number {
if (root === null) return 0;

const queue: TreeNode[] = [root];
let depth = 0;

while (queue.length > 0) {
const levelSize = queue.length; // 锁定当前层节点数
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++; // 完成一层
}

return depth;
}

4. 面试延伸

  • 最小深度(111 题) 的坑:只有一个孩子时,不能简单 min(左, 右),要排除值为 0 的那侧空子树。
  • 平衡二叉树判断(110 题):DFS 求深度时顺带检查任意节点左右子树高度差 ≤ 1,用「自底向上 + 提前终止(返回 -1 作标记)」优化到 O(n)。
  • 树的直径(543 题):求任意两点最长路径,需要在全局记录 左高 + 右高 的最大值,是最大深度的高频变体。
  • 递归三要素:明确返回值含义、写好 base case(null -> 0)、信任递归不需要手动展开。

难度:简单 | LeetCode 104 题 | 二叉树递归入门

1. 题目

给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型左括号。

示例:

1
2
3
4
5
"()"        -> true
"()[]{}" -> true
"(]" -> false
"([)]" -> false
"{[]}" -> true

2. 解题思路

括号匹配是栈的招牌应用场景。核心规律:最近打开的括号,必须最先被闭合(后进先出)。

遍历字符串:

  • 遇到左括号,压栈。
  • 遇到右括号,看栈顶:
    • 栈为空 → 没有可匹配的左括号,false。
    • 栈顶不是对应的左括号 → 顺序或类型错误,false。
    • 匹配成功 → 弹出栈顶。
  • 全部遍历结束后,栈必须为空(所有左括号都被闭合),否则 false。

一个常见优化技巧:遇到右括号时,如果它应该匹配的左括号不在栈顶,立即失败,无需额外判断。

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n),最坏全是左括号。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function isValid(s: string): boolean {
const pairs: Record<string, string> = {
')': '(',
']': '[',
'}': '{',
};
const stack: string[] = [];

for (const ch of s) {
// 右括号:栈顶必须是对应的左括号
if (ch in pairs) {
const top = stack.pop(); // 空数组 pop 返回 undefined,天然处理空栈
if (top !== pairs[ch]) return false;
} else {
// 左括号:入栈
stack.push(ch);
}
}

return stack.length === 0;
}

// 测试
console.log(isValid("{[]}")); // true
console.log(isValid("([)]")); // false
console.log(isValid("(")); // false

4. 面试延伸

  • 最长有效括号(LeetCode 32) 用栈记录下标,求长度;进阶可用 DP,是难题级别。
  • 括号生成(22 题) 是回溯:维护左右括号计数,left < n 加左括号、right < left 加右括号。
  • 有效括号 III / 通配符(1047 删重复) 等都用栈,掌握「遇右查栈顶」这一招就能举一反三。
  • 扩展字符集(如标签嵌套 <div>)时,把 Record 换成 Map 支持多字符 key 即可。

难度:简单 | LeetCode 20 题 | 栈应用第一课

0%