LeetCode 上一道经典的二叉搜索树（BST）题目——530. 二叉搜索树的最小绝对差，这道题看似简单，却能很好地考察我们对 BST 特性的理解，以及二叉树遍历方式的灵活运用。下面我会从题目分析、核心思路、两种解法拆解，到代码细节注释，一步步帮大家搞懂这道题，新手也能轻松跟上。

一、题目解读

题目很直白：给一个二叉搜索树的根节点 root，返回树中任意两个不同节点值之间的最小差值，差值是正数（即两值之差的绝对值）。

这里有个关键前提——二叉搜索树的特性：中序遍历二叉搜索树，得到的序列是严格递增的（假设树中没有重复值，题目未明确说明，但测试用例均满足此条件）。

这个特性是解题的核心！因为递增序列中，任意两个元素的最小差值，一定出现在相邻的两个元素之间。比如序列 [1,3,6,8]，最小差值是 3-1=2，而不是 8-1=7 或 6-3=3。所以我们不需要暴力枚举所有两两组合，只需要在中序遍历的过程中，记录前一个节点的值，与当前节点值计算差值，不断更新最小差值即可。

二、核心解题思路

1. 利用 BST 中序遍历为递增序列的特性，将“任意两节点的最小差值”转化为“中序序列中相邻节点的最小差值”；

2. 遍历过程中，维护两个变量：min（记录当前最小差值，初始值设为无穷大）、pre（记录前一个节点的值，初始值设为负无穷大，避免初始值影响第一次差值计算）；

3. 遍历每个节点时，用当前节点值与pre 计算绝对值差值，更新 min，再将 pre 更新为当前节点值；

4. 遍历结束后，min 即为答案。

接下来，我们用两种最常用的遍历方式实现这个思路：迭代中序遍历（解法1）和递归中序遍历（解法2）。

三、解法一：迭代中序遍历（非递归）

迭代遍历的核心是用“栈”模拟递归的调用过程，避免递归深度过深导致的栈溢出（虽然这道题的测试用例大概率不会出现，但迭代写法更通用，适合处理大型树）。

3.1 代码实现（带详细注释）

// 先定义 TreeNode 类（题目已给出，此处复用）
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 === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

// 解法1：迭代中序遍历
function getMinimumDifference_1(root: TreeNode | null): number {
  // 边界处理：空树返回0（题目中树至少有一个节点？但严谨起见还是判断）
  if (!root) return 0;
  let min = Infinity; // 最小差值，初始为无穷大
  let pre = -Infinity; // 前一个节点的值，初始为负无穷大
  const stack: TreeNode[] = []; // 用于模拟中序遍历的栈
  let curr: TreeNode | null = root; // 当前遍历的节点

  // 第一步：将左子树所有节点压入栈（中序遍历：左 -> 根 -> 右）
  while (curr) {
    stack.push(curr);
    curr = curr.left; // 一直向左走，直到最左节点
  }

  // 第二步：弹出栈顶节点，处理根节点，再遍历右子树
  while (stack.length) {
    const node = stack.pop(); // 弹出栈顶（当前要处理的根节点）
    if (!node) continue; // 防止空节点（理论上不会出现）

    // 处理右子树：将右子树的所有左节点压入栈
    if (node.right) {
      let right: TreeNode | null = node.right;
      while (right) {
        stack.push(right);
        right = right.left;
      }
    }

    // 计算当前节点与前一个节点的差值，更新最小差值
    min = Math.min(min, Math.abs(pre - node.val));
    // 更新pre为当前节点值，为下一个节点做准备
    pre = node.val;
  }

  return min;
};

3.2 思路拆解

1. 初始化：栈用于存储待处理的节点，curr指向根节点，先将根节点的所有左子节点压入栈（因为中序遍历要先访问左子树）；

2. 弹出栈顶节点（此时该节点的左子树已处理完毕），先处理其右子树（将右子树的所有左节点压入栈，保证下一次弹出的是右子树的最左节点）；

3. 计算当前节点与pre的差值，更新min，再将pre更新为当前节点值；

4. 重复上述过程，直到栈为空，遍历结束。

优势：不依赖递归栈，避免递归深度过大导致的栈溢出，空间复杂度由递归的 O(h)（h为树高）优化为 O(h)（栈的最大深度也是树高），实际运行更稳定。

四、解法二：递归中序遍历

递归写法更简洁，代码量少，思路也更直观，适合树的深度不大的场景。核心是用递归函数实现中序遍历的“左 -> 根 -> 右”顺序。

4.1 代码实现（带详细注释）

// 解法2：递归中序遍历
function getMinimumDifference_2(root: TreeNode | null): number {
  if (!root) return 0;
  let min = Infinity; // 最小差值
  let pre = -Infinity; // 前一个节点的值

  // 递归函数：实现中序遍历
  const dfs = (node: TreeNode) => {
    if (!node) return; // 递归终止条件：节点为空

    // 1. 遍历左子树（左）
    if (node.left) dfs(node.left);

    // 2. 处理当前节点（根）：计算差值，更新min和pre
    min = Math.min(min, Math.abs(pre - node.val));
    pre = node.val;

    // 3. 遍历右子树（右）
    if (node.right) dfs(node.right);
  }

  // 从根节点开始递归
  dfs(root);
  return min;
};

4.2 思路拆解

1. 定义递归函数 dfs，参数为当前节点，负责遍历以该节点为根的子树；

2. 递归终止条件：当前节点为空，直接返回；

3. 先递归遍历左子树（保证左子树先被处理）；

4. 处理当前节点：计算当前节点与pre的差值，更新min，再将pre更新为当前节点值；

5. 最后递归遍历右子树；

6. 从根节点调用dfs，完成整个树的遍历，返回min。

优势：代码简洁，思路直观，容易理解和编写；劣势：当树的深度很大时（如链式树），会出现递归栈溢出，此时迭代写法更合适。

五、两种解法对比与总结

解法	遍历方式	时间复杂度	空间复杂度	优势	劣势
解法1	迭代中序	O(n)（每个节点遍历一次）	O(h)（h为树高，栈的最大深度）	稳定，无栈溢出风险，通用	代码稍长，需要手动维护栈
解法2	递归中序	O(n)（每个节点遍历一次）	O(h)（递归栈深度）	代码简洁，思路直观，易编写	深度过大时会栈溢出

关键总结

1. 这道题的核心是利用 BST 中序遍历为递增序列，将“任意两节点最小差值”转化为“相邻节点最小差值”，避免暴力枚举；

2. 两种解法的核心逻辑一致，只是遍历方式不同，可根据树的深度选择：树深较小时用递归，树深较大时用迭代；

3. 注意初始值的设置：min设为无穷大（保证第一次差值能更新min），pre设为负无穷大（避免初始值与第一个节点值计算出不合理的差值）；

4. 边界处理：空树返回0（题目中树至少有一个节点，但严谨起见必须判断）。

六、拓展思考

如果这道题不是 BST，而是普通二叉树，该怎么解？

答案：先遍历所有节点，将节点值存入数组，再对数组排序，计算相邻元素的最小差值。时间复杂度 O(n log n)（排序耗时），空间复杂度 O(n)（存储所有节点值），效率低于本题的解法，由此可见利用数据结构特性解题的重要性。

好了，这道题的两种解法就讲解完毕了。希望大家能通过这道题，加深对 BST 特性和二叉树中序遍历的理解，下次遇到类似题目能快速想到解题思路。

在 TypeScript 的日常开发中，我们经常为了灵活性而将接口（Interface）或类型（Type）的属性定义为可选（使用 ? 修饰符）。但在某些特定场景下，例如配置初始化完成、表单提交前验证或 API 响应处理后，我们需要确保这些属性已经存在，即将其转换为“必选”状态。

这种转换不仅能提供更好的代码提示，还能在编译阶段规避大量的 null 或 undefined 检查。本文将由浅入深介绍四种主流的转换方案。

1. 全局转换：使用内置工具类型 Required<T>

TypeScript 自 2.8 版本起引入了 Required<T>，这是最直接的方案。它会遍历类型 T 的所有属性，并移除每个属性末尾的可选修饰符。

interface UserProfile {
  id: string;
  name?: string;
  email?: string;
}

// 转换后：id, name, email 全部变为必选
type StrictUser = Required<UserProfile>;

const user: StrictUser = {
  id: "001",
  name: "张三",
  email: "zhangsan@example.com" // 缺少任何一个都会报错
};

适用场景：当你需要对整个对象进行“严格化”处理时，这是首选方案。

---

2. 精准打击：仅转换特定属性为必选

在实际业务中，我们往往只需要确保某几个关键字段存在，而保留其他字段的可选性。这时可以结合 Pick、Omit 和 Required 构建一个复合工具类型。

我们可以定义一个通用的 MarkRequired 类型：

/**
 * T: 原类型
 * K: 需要转为必选的键名联合类型
 */
type MarkRequired<T, K extends keyof T> = 
  Omit<T, K> & Required<Pick<T, K>>;

interface Config {
  host?: string;
  port?: number;
  protocol?: 'http' | 'https';
}

// 示例：仅让 host 变为必选，port 和 protocol 依然可选
type EssentialConfig = MarkRequired<Config, 'host'>;

const myConfig: EssentialConfig = {
  host: "localhost" // port 和 protocol 可选填
};

原理解析：该方法先用 Omit 剔除目标属性，再用 Pick 选出目标属性并通过 Required 转为必选，最后通过交叉类型 & 进行合并。

---

3. 深入底层：使用映射类型中的 -? 符号

如果你正在尝试编写自己的类型库，了解映射类型（Mapped Types）的修饰符至关重要。在 TypeScript 中，+ 和 - 可以作为前缀应用于 ? 或 readonly 修饰符。

type MyRequired<T> = {
  // -? 表示显式地移除可选属性标记
  [P in keyof T]-?: T[P];
};

// 与此相对，+?（通常简写为 ?）用于增加可选标记
type MyPartial<T> = {
  [P in keyof T]+?: T[P];
};

技术要点：使用 -? 是 Required<T> 的底层实现原理。它不仅能去除问号，在处理一些复杂的条件类型映射时，这种手动控制的能力非常强大。

---

4. 函数参数与深度嵌套处理

函数参数转换

对于函数，最稳妥的方法是在重载或重新定义时直接移除 ?。但在高阶函数或泛型约束中，如果你想约束传入的函数必须接受必选参数，可以利用上述类型工具。

深度嵌套（Deep Required）

内置的 Required 只能处理第一层属性。如果对象是深层嵌套的，你需要递归处理：

type DeepRequired<T> = {
  [P in keyof T]-?: T[P] extends object 
    ? DeepRequired<T[P]> 
    : T[P];
};

interface NestedConfig {
  db?: {
    user?: string;
    pwd?: string;
  }
}

type StrictNested = DeepRequired<NestedConfig>;

建议：在处理极其复杂的深层转换时，推荐使用社区成熟的库如 ts-essentials，其 DeepRequired 经过了大量边缘情况的验证。

---

结论与行动建议

根据不同的工程需求，建议采取以下策略：

1. 立即可做：检查项目中的配置对象或 API 聚合层，使用 Required<T> 替代繁琐的非空断言（!）。
2. 最佳实践：为了保持代码的 DRY（Don't Repeat Yourself）原则，建议在项目的 types/utils.d.ts 中收藏 MarkRequired 工具类型，用于处理部分属性必选的场景。
3. 注意性能：过度使用复杂的递归类型（如 DeepRequired）可能会增加 TypeScript 编译器的负担，在大型项目中应谨慎评估其影响范围。

很多人学了半年 TS，代码里清一色 any，偶尔来个 string | number，然后在简历上写"熟练使用 TypeScript"。这篇文章，就是为了让你彻底告别这种状态。

先说清楚一件事：TypeScript 的类型系统到底在解决什么问题

JavaScript 是动态类型语言。变量可以今天是字符串，明天是数字，后天变成 undefined。这在小项目里无所谓，但一旦代码规模上来——比如一个有 50 个接口、20 个开发者协作的中大型前端项目——没有类型约束，就像在没有红绿灯的十字路口开车，每一次函数调用都是一次赌博。

TypeScript 的本质是在编译阶段拦截这些赌局。它不改变运行时行为，但能在你写代码的那一刻，就告诉你哪里会出问题。

理解了这一点，再来看各种类型，你就不会觉得它们是语法糖，而是协议——你和编译器之间的协议，你和团队成员之间的协议。

一、基础类型：别觉得简单，细节决定成败

string / number / boolean

这三个是 TS 里用得最多的类型，也是最容易被忽视的。

let name: string = "Andy";
let age: number = 18;
let isLogin: boolean = false;

看起来平平无奇，但"类型安全"的价值在这里：

let name: string = "andy";
name.toUpperCase(); // ✅ 合法，string 有这个方法
name.toFixed();     // ❌ 直接报错，string 没有 toFixed

换成纯 JS，这个错误只会在运行时才被发现——可能是用户触发了某个边界条件，可能是在生产环境，可能是在凌晨三点。TS 把运行时错误前移到了编写时，这是它最核心的价值。

null 和 undefined 的处理是门学问

很多项目踩过这样的坑：后端接口返回的某个字段"理论上有值"，但有时候会是 null。如果你的类型定义是 string，编译器不会报错，但运行时一旦拿到 null 去调用字符串方法，直接崩。

正确姿势：

interface User {
  nickname: string | null; // 明确告诉所有人：这个字段可能为空
}

这样当你试图直接调用 user.nickname.toUpperCase() 时，编译器会强制你先处理 null 的情况。这不是麻烦，这是把锅甩给编译器而不是留给用户。

bigint：什么时候才需要它

JavaScript 的 number 类型基于 IEEE 754 双精度浮点数，能精确表示的最大整数是 2^53 - 1，也就是 9007199254740991。超过这个数，精度会丢失。

let big: bigint = 9007199254740991n; // 注意末尾的 n

金融系统、密码学、需要处理超大 ID 的场景才会用到它。普通业务开发遇到的机会不多，但知道它存在，不会在某天看到 n 结尾的数字一脸懵。

二、字面量类型与联合类型：从"能用"到"好用"的关键一跳

字面量类型

type Direction = "left" | "right" | "up" | "down";

function move(dir: Direction) {
  // ...
}

如果参数类型是 string，你传 "diagonal" 进去编译器不会说话。但用字面量联合类型，"diagonal" 直接飘红。类型越窄，保护越强。

这个思路很重要：在你确定某个值只会是有限几种可能的时候，不要偷懒用 string，用字面量联合类型把范围锁死。

联合类型与类型缩小（Type Narrowing）

联合类型（Union）表示"这个值可能是 A，也可能是 B"：

function print(val: string | number) {
  if (typeof val === "string") {
    console.log(val.toUpperCase()); // 这里 TS 已经知道 val 是 string
  } else {
    console.log(val.toFixed(2));    // 这里 TS 已经知道 val 是 number
  }
}

这叫类型缩小（Type Narrowing）——通过条件判断，编译器会在不同分支里自动推断出更精确的类型。理解这个机制，是写出干净 TS 代码的前提。

交叉类型（Intersection）

联合是"或"，交叉是"且"：

type User = { name: string; email: string };
type Admin = User & { role: "admin"; permissions: string[] };

Admin 必须同时满足 User 和后面那个对象的结构。在实际项目里，这是组合模块类型的利器，比继承更灵活，比重新定义更省力。

三、any、unknown、never：三个经常被误用的类型

any：能不用就不用

let x: any;
x.foo.bar.baz(); // 不报错，但运行时爆炸

any 是类型系统的逃生舱。它告诉编译器"别管我，我自己负责"。偶尔处理真的无法预知结构的数据，或者接入没有类型声明的第三方库，可以用。但如果你的代码里 any 满天飞，TypeScript 就成了摆设——你得到了所有 TS 的编译复杂度，却没有得到任何类型安全。

unknown：any 的负责任替代品

unknown 同样表示"不知道是什么类型"，但它要求你在使用前必须先做类型检查：

let x: unknown;

if (typeof x === "string") {
  x.toUpperCase(); // ✅ 通过检查后才能用
}

x.toUpperCase(); // ❌ 直接报错

处理外部输入、API 响应、用户数据时，unknown 是比 any 更安全的选择。

never：表示"这里不应该被执行到"

never 有两个核心用途：

1. 表示函数不会正常返回

function throwError(msg: string): never {
  throw new Error(msg);
}

2. 穷举检查（Exhaustive Check）——这个才是精髓

type Direction = "up" | "down" | "left";

function move(dir: Direction) {
  if (dir === "up") { /* ... */ }
  else if (dir === "down") { /* ... */ }
  else if (dir === "left") { /* ... */ }
  else {
    const _check: never = dir;
    // 如果未来 Direction 加了 "right" 但这里没处理
    // 编译器会在这行报错，提醒你补全逻辑
  }
}

这是一个防御性编程技巧：让编译器帮你检查所有情况是否都被覆盖。在处理状态机、分支逻辑密集的业务代码里，能避免非常隐蔽的 bug。

四、泛型：类型系统的"函数"

泛型（Generic）是 TypeScript 类型系统里最有表达力的特性。你可以把它理解成类型层面的参数——函数接受值的参数，泛型接受类型的参数。

function identity<T>(value: T): T {
  return value;
}

identity<string>("hello"); // 返回类型是 string
identity<number>(42);      // 返回类型是 number

进一步，泛型可以加约束：

function getLength<T extends { length: number }>(val: T): number {
  return val.length;
}

getLength("hello");    // ✅ string 有 length
getLength([1, 2, 3]);  // ✅ array 有 length
getLength(123);        // ❌ number 没有 length，报错

泛型约束用 extends 关键字，表示"T 必须满足某个结构"。这让你写出的工具函数既灵活又安全。

五、工具类型：不要重复造轮子

TS 内置了一批工具类型（Utility Types） ，专门用于对已有类型进行变形。掌握这些，能让你的类型定义简洁一个量级。

Partial：把所有字段变成可选

interface User {
  id: string;
  name: string;
  email: string;
}

type UpdateUserPayload = Partial<User>;
// 等价于 { id?: string; name?: string; email?: string }

更新接口往往只需要传部分字段，Partial 比重新定义一个新 interface 优雅得多。

Pick 和 Omit：精确裁剪类型

type UserPreview = Pick<User, "id" | "name">;
// 只保留 id 和 name

type PublicUser = Omit<User, "password" | "internalNotes">;
// 去掉敏感字段

这两个是一对互补工具。前端展示层经常需要的"脱敏版接口类型"，用 Omit 一行搞定。

Record：快速定义映射结构

const userCache: Record<string, User> = {};
// 等价于 { [key: string]: User }

Record<K, V> 比写索引签名更直观。后台管理系统里的权限映射、字典数据、配置对象，Record 用起来非常顺手。

Exclude 和 Extract：在联合类型里做集合运算

type Status = "active" | "inactive" | "banned";

type ActiveStatus = Extract<Status, "active" | "inactive">;
// 结果："active" | "inactive"

type NonBanned = Exclude<Status, "banned">;
// 结果："active" | "inactive"

Extract 是取交集，Exclude 是取差集。在处理复杂状态枚举时会用到。

六、条件类型与映射类型：进阶但值得了解

条件类型

type IsString<T> = T extends string ? true : false;

type A = IsString<string>; // true
type B = IsString<number>; // false

语法和三元运算符一样，但它运作在类型层面。很多 TS 内置的工具类型（比如 Exclude）底层就是用条件类型实现的。

映射类型

type Readonly<T> = {
  readonly [K in keyof T]: T[K];
};

keyof T 拿到 T 的所有键，in 遍历它们，然后给每个键加上 readonly 修饰符。Partial、Required、Readonly 这些内置工具类型，背后全是映射类型。

七、interface vs type：别被这个问题困扰太久

这是 TS 社区里被讨论烂了的问题，结论其实挺简单：

用 interface 定义对象结构，因为它支持声明合并（Declaration Merging） ——同名 interface 会自动合并，这在扩展第三方库类型时很有用。

用 type 定义联合类型、交叉类型、别名，因为 interface 做不到 type Status = "active" | "inactive" 这种写法。

// interface：适合对象，支持 extends 和合并
interface User {
  name: string;
}
interface User {
  age: number; // 合并生效，不报错
}

// type：更灵活，适合联合/交叉/别名
type ID = string | number;
type AdminUser = User & { role: "admin" };

实际项目里，两者往往混用。不必教条，根据场景选最合适的。

八、总结表

以下 12 个类型/特性，覆盖了日常前端开发 90% 以上的场景：

类型 / 特性	核心价值
string / number / boolean	基础约束，防止类型误用
联合类型	处理多态数据，配合类型缩小使用
interface	定义数据结构，团队协作的契约
type	定义联合、交叉、别名，比 interface 更灵活
泛型 <T>	复用逻辑的同时保持类型安全
Record	快速定义映射/字典结构
Partial	更新接口的标配
Pick / Omit	从已有类型裁剪出你需要的形状
never	穷举检查，让编译器替你兜底

结语

TypeScript 的类型系统不是负担，是把 bug 消灭在编辑器里的机会。每一个精确的类型定义，都是在为未来的自己、为团队省下一次排查 bug 的时间。

从今天起，遇到 any，先想想能不能换成 unknown。遇到 string，先想想能不能换成字面量联合类型。把类型写得越具体，编译器能帮你做的就越多。

TypeScript 最好的使用方式，是把它当成一个不会累、不会忘、全年无休的代码审查员。

同学们好，我是 Eugene（尤金），一个拥有多年中后台开发经验的前端工程师~

（Eugene 发音很简单，/juːˈdʒiːn/，大家怎么顺口怎么叫就好）

你是否也有过：明明学过很多技术，一到关键时候却讲不出来、甚至写不出来？

你是否也曾怀疑自己，是不是太笨了，明明感觉会，却总差一口气？

就算想沉下心从头梳理，可工作那么忙，回家还要陪伴家人。

一天只有24小时，时间永远不够用，常常感到力不从心。

技术行业，本就是逆水行舟，不进则退。

如果你也有同样的困扰，别慌。

从现在开始，跟着我一起心态归零，利用碎片时间，来一次彻彻底底的基础扫盲。

这一次，我们一起慢慢来，扎扎实实变强。

不搞花里胡哨的理论堆砌，只分享看得懂、用得上的前端干货，

咱们一起稳步积累，真正摆脱“面向搜索引擎写代码”的尴尬。

一、开篇：为什么要关心 TS 类型？

日常业务里经常会遇到：

• 类型报错：Object is possibly 'undefined'、Type 'string' is not assignable to type 'number'
• 不知道选什么：any、unknown、interface、type 什么时候用？
• 写了很多 TS 却像在写 JS：到处用 any，类型形同虚设

TypeScript 的核心是「类型约束」，把很多问题在编译期暴露出来。但很多人要么写太多类型最后变玄学，要么只会 any，形同 JS。

这篇文章不讲特别深的底层原理，而是围绕：平时写业务时该怎么选、为什么这么选、容易踩哪些坑。从基础类型 → 接口 → 类型别名 → 实战选型 → 踩坑，一次性理清。

二、基础类型扫盲

先把日常最常用的 5 个类型搞清楚。

类型	含义	典型用途
string	字符串	文案、id、枚举值
number	数字（含整数、浮点、NaN）	数量、金额、分页
boolean	布尔	开关、状态
any	任意类型，不做检查	兼容老代码、临时兜底
unknown	任意类型，但必须先检查再用	比 any 更安全的兜底

2.1 string / number / boolean

这三个是基础原始类型，和 JS 里的用法一致，只是加了一层类型标注：

// 变量声明时标注类型
const name: string = '张三';
const age: number = 25;
const isActive: boolean = true;

// 函数参数和返回值
function greet(name: string): string {
  return `你好，${name}`;
}

function add(a: number, b: number): number {
  return a + b;
}

业务里怎么用：接口返回值、表单字段、状态开关，优先用这三个而不是 any。

2.2 any：最自由也最危险

any 表示「任意类型」，TS 不再做类型检查。

let data: any = 'hello';
data = 123;        // OK
data = { a: 1 };   // OK
data.toUpperCase(); // 编译通过，但运行时报错！data 实际是 number

问题：any 会关闭类型检查，等于回到裸写 JS，很容易在运行时才发现错误。

适用场景：

• 临时接入老接口、第三方库，还没时间写类型
• 快速迁移 JS 项目到 TS 时的过渡
• 已经用 try-catch 等做了安全兜底

建议：能不用就不用，用的话尽量加注释说明原因。

2.3 unknown：比 any 更安全的兜底

unknown 也表示「任意类型」，但使用时必须先「收窄」类型，否则不能直接用。

let data: unknown = getFromApi(); // 不知道接口返回什么

// 直接调用会报错
// data.toString();  // Error: 'data' is of type 'unknown'

// 先判断类型再使用
if (typeof data === 'string') {
  console.log(data.toUpperCase()); // OK
} else if (typeof data === 'object' && data !== null && 'name' in data) {
  console.log((data as { name: string }).name); // 收窄后可安全使用
}

和 any 的对比：

特性	any	unknown
可直接调用方法	✅	❌ 必须先收窄
可赋给任意类型	✅	❌
类型安全	无	有（需检查后才用）

建议：拿不到确切类型时，用 unknown 代替 any，通过 typeof、in、类型守卫等方式收窄后再用。

三、interface：描述对象形状

interface 用来描述「对象长什么样」：有哪些属性、什么类型、哪些可选。

3.1 基本用法

// 定义用户接口
interface User {
  id: number;
  name: string;
  age?: number;  // 可选属性
}

// 使用
const user: User = {
  id: 1,
  name: '张三'
  // age 可省略
};

3.2 可选属性、只读属性

interface Config {
  readonly apiUrl: string;  // 只读，不能改
  timeout?: number;         // 可选
}

const config: Config = { apiUrl: 'https://api.example.com' };
// config.apiUrl = 'xxx';  // Error: 只读

3.3 继承

interface BaseUser {
  id: number;
  name: string;
}

interface AdminUser extends BaseUser {
  role: 'admin';
  permissions: string[];
}

const admin: AdminUser = {
  id: 1,
  name: '管理员',
  role: 'admin',
  permissions: ['read', 'write']
};

3.4 索引签名（动态属性）

// 属性名是 string，值是 number
interface StringMap {
  [key: string]: number;
}

const map: StringMap = {
  a: 1,
  b: 2
};

业务场景：后端返回的用户、列表项、配置对象等，用 interface 描述结构最合适。

四、type 类型别名：给类型起个名字

type 用来给任意类型起别名，可以是基础类型、对象、联合类型、函数等。

4.1 基本用法

// 基础类型别名
type UserId = number;
type UserName = string;

// 对象类型
type User = {
  id: UserId;
  name: UserName;
};

// 联合类型（常见于业务）
type Status = 'pending' | 'success' | 'error';
type Theme = 'light' | 'dark';

4.2 联合类型、交叉类型

// 联合：A 或 B
type Result = { success: true; data: any } | { success: false; error: string };

// 交叉：A 且 B 的属性合并
type WithTimestamp = User & { createdAt: Date };

4.3 函数类型

type OnChange = (value: string) => void;
type FetchUser = (id: number) => Promise<User>;

业务场景：状态枚举、回调类型、联合类型等，用 type 更合适。

五、interface vs type：怎么选？

这是问得最多的一个问题，先看核心区别：

特性	interface	type
声明合并	✅ 同名可合并	❌ 同名会报错
继承	extends	& 交叉类型
适用对象	对象结构	任意类型
扩展对象	容易	容易
联合/交叉	不常用	常用

5.1 声明合并（interface 独有）

// interface 同名会合并
interface User {
  name: string;
}
interface User {
  age: number;
}
// 等价于 { name: string; age: number }

// type 同名会报错
type User = { name: string };
type User = { age: number };  // Error: 重复声明

业务含义：写插件、扩展第三方类型定义时，用 interface 可以多次补充属性；而 type 只能定义一次。

5.2 选型建议

用 interface：

• 描述对象结构（用户、配置、接口返回值等）
• 有继承需求（如 extends BaseUser）
• 可能被第三方或插件扩展（依赖声明合并）

用 type：

• 联合类型：'pending' | 'success' | 'error'
• 交叉类型：User & { role: string }
• 函数类型：(id: number) => Promise<User>
• 元组、复杂组合类型

实践中：对象结构优先 interface，其它复杂类型用 type。两者都能描述对象时，很多团队会统一用 interface，可读性更好。

六、实战场景：该怎么写

6.1 接口返回值

// 用 interface 描述
interface UserListItem {
  id: number;
  name: string;
  avatar?: string;
  status: 'active' | 'inactive';
}

interface ApiResponse<T> {
  code: number;
  message: string;
  data: T;
}

// 使用
async function fetchUserList(): Promise<ApiResponse<UserListItem[]>> {
  const res = await axios.get('/api/users');
  return res.data;
}

6.2 表单、状态枚举

// 用 type 做联合
type FormStatus = 'draft' | 'submitting' | 'success' | 'error';
type SortOrder = 'asc' | 'desc';

interface FilterState {
  status: FormStatus;
  sortBy: string;
  sortOrder: SortOrder;
}

6.3 事件回调

type OnSearch = (keyword: string) => void;
type OnPageChange = (page: number, size: number) => void;

interface TableProps {
  onSearch: OnSearch;
  onPageChange: OnPageChange;
}

6.4 拿不准类型时用 unknown

async function fetchData(url: string): Promise<unknown> {
  const res = await fetch(url);
  return res.json();
}

// 使用时必须收窄
const data = await fetchData('/api/config');
if (data && typeof data === 'object' && 'theme' in data) {
  const theme = (data as { theme: string }).theme;
  // 安全使用
}

七、踩坑指南

坑	原因	建议
到处用 any，类型失效	any 关闭类型检查	尽量用 unknown，或用具体类型
Object is possibly 'undefined'	可能为 undefined 却直接访问	可选链 obj?.prop、if 判断、! 断言
interface 和 type 混用一团	团队没约定	对象用 interface，联合/函数用 type
对象字面量多了属性报错	多余属性检查	用变量接收再传入，或加索引签名
第三方库没有类型	老库、非 TS 编写	写 .d.ts 或 @ts-ignore，标注原因

7.1 多余属性检查

interface User {
  id: number;
  name: string;
}

// 直接传字面量时，多了属性会报错
// createUser({ id: 1, name: '张三', age: 18 });  // Error

// 用变量接收再传则不会（会按结构兼容）
const user = { id: 1, name: '张三', age: 18 };
createUser(user);  // OK

7.2 类型断言要谨慎

// as 断言：你说它是什么，TS 就信
const data = getData() as User;  // 若实际不是 User，运行时可能崩

// 更安全的做法：用类型守卫
function isUser(obj: unknown): obj is User {
  return obj !== null && typeof obj === 'object' && 'id' in obj && 'name' in obj;
}

八、小结

概念	一句话	典型场景
string/number/boolean	基础类型，优先用	接口字段、函数参数、状态
any	任意类型，无检查	临时兜底、兼容老代码，少用
unknown	任意类型，用前须收窄	拿不准类型时的安全选择
interface	描述对象结构	用户、配置、接口返回值
type	类型别名，可联合/交叉	状态枚举、函数类型、复杂组合

记住三点：

1. 能用具体类型就不用 any，拿不准就用 unknown 再收窄。
2. 对象结构用 interface，联合/函数/复杂类型用 type。
3. 业务里够用就行，不必一开始就追求完美，先让类型系统帮你兜住大部分错误。

把类型选对，编译期就能发现很多问题，后面的重构和维护都会轻松很多。

---

学习本就是一场持久战，不需要急着一口吃成胖子。哪怕今天你只记住了一点点，这都是实打实的进步。

后续我还会继续用这种大白话、讲实战方式，带大家扫盲更多前端基础。

关注我，不迷路，咱们把那些曾经模糊的知识点，一个个彻底搞清楚。

如果你觉得这篇内容对你有帮助，不妨点赞收藏，下次写代码卡壳时，拿出来翻一翻，比搜引擎更靠谱。

我是 Eugene，你的电子学友，我们下一篇干货见～

LeetCode经典二叉树题目——102. 二叉树的层序遍历，这道题是二叉树广度优先搜索（BFS）的入门必刷题，也是面试中高频出现的基础题，不管是新手还是复盘，都值得好好吃透。

话不多说，先看题目本身，帮大家理清题意、拆解思路，再逐行解析代码，最后总结易错点，确保看完就能上手写对。

一、题目解读：什么是层序遍历？

题目给出二叉树的根节点root，要求返回其节点值的层序遍历，核心要求是「逐层地，从左到右访问所有节点」。

举个简单例子帮助理解：

如果二叉树是：

    3
   / \
  9  20
    /  \
   15   7

那么层序遍历的结果就是 [[3], [9,20], [15,7]] —— 第一层只有根节点3，第二层从左到右是9和20，第三层是15和7，每一层的节点值单独作为一个数组，最终组成二维数组返回。

这里要注意和「前中后序遍历」区分开：前中后序是深度优先（DFS），沿着一条路径走到底再回溯；而层序遍历是广度优先（BFS），先遍历完当前层的所有节点，再进入下一层，像“剥洋葱”一样逐层推进。

二、核心思路：用队列实现BFS

层序遍历的核心难点是「区分每一层的节点」—— 如何知道当前遍历的是哪一层，什么时候结束当前层、进入下一层？

解决这个问题的关键工具是「队列」（先进先出，FIFO），队列的特性刚好契合层序遍历“先遍历当前层所有节点，再处理下一层”的逻辑，具体思路分4步：

1. 边界处理：如果根节点root为null，直接返回空数组（空树没有节点可遍历）；

2. 初始化：创建一个队列，将根节点入队（队列存储当前待处理的节点）；创建一个结果数组，用于存储每一层的节点值；

3. 循环处理（直到队列为空）：

   • 记录当前队列的长度（也就是当前层的节点个数，记为levelSize），这个长度是区分层的关键；

   • 创建一个临时数组level，用于存储当前层的所有节点值；

   • 循环levelSize次，每次从队列头部取出一个节点：

     • 将该节点的值加入临时数组level；

     • 如果该节点有左孩子，将左孩子入队（为下一层遍历做准备）；

     • 如果该节点有右孩子，将右孩子入队（同样为下一层遍历做准备）；

   • 当前层遍历完成，将临时数组level加入结果数组；

4. 循环结束，返回结果数组。

这里的核心技巧是「记录当前层的节点个数」—— 因为队列中会不断加入下一层的节点，只有通过levelSize限制循环次数，才能确保每次循环只处理当前层的节点，不会混入下一层的节点，从而正确区分每一层。

三、完整代码+逐行解析

先给出完整可运行的TypeScript代码（题目已提供TreeNode类，直接复用即可），再逐行拆解关键逻辑，新手也能看懂每一步的作用。

完整代码

/**
 * Definition for a binary tree node.
 * 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===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

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 === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function levelOrder(root: TreeNode | null): number[][] {
  // 边界处理：空树返回空数组
  if (!root) {
    return []
  }
  // 队列：存储当前待处理的节点，初始入队根节点
  const queue: TreeNode[] = [root]
  // 结果数组：存储每一层的节点值
  const result: number[][] = []
  // 队列不为空，说明还有节点未处理
  while (queue.length) {
    // 记录当前层的节点个数（关键：区分每一层）
    const levelSize = queue.length
    // 临时数组：存储当前层的节点值
    const level: number[] = []
    // 循环处理当前层的所有节点（循环次数 =  当前层节点数）
    for (let i = 0; i < levelSize; i++) {
      // 从队列头部取出节点（先进先出）
      const node = queue.shift()
      // 防止node为null（理论上不会出现，严谨性处理）
      if (!node) continue;
      // 将当前节点值加入当前层数组
      level.push(node.val)
      // 左孩子存在，入队（下一层节点）
      if (node.left) {
        queue.push(node.left)
      }
      // 右孩子存在，入队（下一层节点）
      if (node.right) {
        queue.push(node.right)
      }
    }
    // 当前层处理完毕，加入结果数组
    result.push(level)
  }
  // 返回最终结果
  return result;
};

逐行关键解析

1. 边界处理 if (!root) return []： 如果根节点为null，说明是一棵空树，没有任何节点，直接返回空数组，避免后续队列操作报错。

2. 队列初始化 const queue: TreeNode[] = [root]： 队列是核心数据结构，初始时只有根节点，因为层序遍历从根节点开始。

3. 循环条件 while (queue.length)： 只要队列不为空，就说明还有节点没处理（可能是当前层剩余节点，也可能是下一层节点），循环继续。

4. 记录当前层节点数 const levelSize = queue.length： 这是最关键的一步！假设当前队列中有3个节点，说明当前层有3个节点，后续循环3次，刚好把这3个节点处理完，不会混入下一层的节点。

5. 临时数组 const level: number[] = []： 每一层都需要一个临时数组存储节点值，遍历完当前层后，将这个数组加入结果数组，保证结果的二维结构。

6. 取出节点 const node = queue.shift()： shift()方法会删除并返回队列的第一个元素，契合队列“先进先出”的特性，确保先处理当前层的第一个节点（从左到右）。

7. 左、右孩子入队： 处理完当前节点后，将其左、右孩子（如果存在）入队，这些孩子是下一层的节点，会在后续循环中被处理，从而实现“逐层遍历”。

8. 加入结果数组 result.push(level)： 当前层的所有节点都处理完毕后，将临时数组level加入result，完成一层的遍历。

四、易错点提醒（避坑必看）

这道题看似简单，但新手很容易踩坑，总结3个最常见的错误，帮大家避开：

1. 忘记记录levelSize，直接循环queue.length： 错误原因：队列在循环中会不断加入下一层的节点，queue.length会动态变化，导致循环次数不对，无法区分层。正确做法：必须在每次while循环开始时，记录当前queue的长度（即levelSize），循环次数固定为levelSize。

2. 忽略node为null的情况： 错误原因：虽然题目中root是TreeNode|null，但queue中理论上不会有null，但shift()方法在队列空时会返回undefined，加上if (!node) continue是严谨性处理，避免报错。

3. 左、右孩子入队顺序错误： 错误原因：题目要求“从左到右”访问，若先入队右孩子、再入队左孩子，会导致当前层节点顺序颠倒。正确做法：先入队左孩子，再入队右孩子，确保左在前、右在后。

五、题目延伸与思考

这道题是层序遍历的基础版本，掌握后可以尝试它的变形题，巩固BFS思路：

• LeetCode 107. 二叉树的层序遍历II：要求自底向上层序遍历（从最下层到最上层），只需将result数组反转即可；

• LeetCode 199. 二叉树的右视图：层序遍历中，每次只保留当前层的最后一个节点值；

• LeetCode 637. 二叉树的层平均值：层序遍历中，计算每一层的节点值平均值。

其实这些变形题的核心思路和本题一致，都是用队列实现BFS，只是在处理“每一层结果”时做了不同的操作，掌握了基础，变形题就能迎刃而解。

六、总结

LeetCode 102题的核心是「用队列实现BFS，通过记录当前层节点数区分每一层」，整体难度中等，是二叉树BFS的入门题。

关键记住3点：队列存节点、levelSize分层次、左孩子先入队，再结合边界处理和严谨性判断，就能轻松AC。

如果是新手，建议自己手动模拟一遍队列的操作过程（比如用上面举的例子，一步步推进队列、处理节点），能更直观地理解层序遍历的逻辑。

在二叉树的算法题型中，“根据遍历序列构造二叉树”是经典考点，而 LeetCode 105 题——从前序与中序遍历序列构造二叉树，更是这一考点的核心代表。这道题不仅能考察我们对二叉树遍历规则的理解，还能检验递归思维和哈希表优化的应用，今天就来一步步拆解这道题，从思路到代码，吃透每一个细节。

一、题目回顾

题目给出两个整数数组preorder 和 inorder，其中 preorder 是二叉树的先序遍历序列，inorder 是同一棵二叉树的中序遍历序列，要求我们构造这棵二叉树并返回其根节点。

补充基础：二叉树遍历规则

• 先序遍历（preorder）：根节点 → 左子树 → 右子树（根在前，左右在后）；

• 中序遍历（inorder）：左子树 → 根节点 → 右子树（根在中间，左右分居两侧）。

核心关键：先序遍历的第一个元素一定是二叉树的根节点；而中序遍历中，根节点左侧的所有元素是左子树的中序序列，右侧的所有元素是右子树的中序序列。利用这两个特性，我们就能递归地构造出整个二叉树。

二、解题思路（核心逻辑）

这道题的解题核心是「递归分治」，配合哈希表优化查找效率，具体思路可以分为 4 步，我们结合例子来理解（假设 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]）：

步骤1：确定根节点

根据先序遍历规则，preorder 的第一个元素 preorder[0] 就是整个二叉树的根节点（例子中根节点是 3）。

步骤2：划分左右子树的中序序列

在中序序列 inorder 中找到根节点的索引（例子中 3 的索引是 1）：

• 根节点左侧的元素（[9]）：左子树的中序序列；

• 根节点右侧的元素（[15,20,7]）：右子树的中序序列。

步骤3：划分左右子树的先序序列

左右子树的节点数量，在中序序列和先序序列中是一致的：

• 左子树的节点数 = 根节点在中序的索引 - 中序序列的起始索引（例子中 1 - 0 = 1，左子树有 1 个节点）；

• 因此，先序序列中，根节点之后的「左子树节点数」个元素（[9]）是左子树的先序序列；

• 剩下的元素（[20,15,7]）是右子树的先序序列。

步骤4：递归构造左右子树

对左子树和右子树，重复上述 3 个步骤：找到子树的根节点、划分左右子序列，直到序列为空（递归终止条件），最终拼接出整个二叉树。

优化点：哈希表加速查找

如果每次在中序序列中查找根节点都用遍历的方式，时间复杂度会达到 O(n²)（n 是节点总数）。我们可以提前用哈希表（Map）存储中序序列中「元素 → 索引」的映射，这样每次查找根节点的索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

先给出 TreeNode 类的定义（题目已提供，此处复用并补充注释），再实现核心的 buildTree 函数，每一步代码都附上详细注释，方便理解：

// 二叉树节点类定义
class TreeNode {
  val: number
  left: TreeNode | null  // 左子节点，默认为null
  right: TreeNode | null // 右子节点，默认为null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val) // 节点值，默认0
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 1. 构建中序序列的哈希映射，key是节点值，value是对应索引
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  /**
   * 递归辅助函数：构造当前范围内的二叉树
   * @param preorderStart 先序序列当前范围的起始索引
   * @param preorderEnd 先序序列当前范围的结束索引
   * @param inorderStart 中序序列当前范围的起始索引
   * @param inorderEnd 中序序列当前范围的结束索引
   * @returns 当前范围的二叉树根节点
   */
  const helper = (
    preorderStart: number, 
    preorderEnd: number, 
    inorderStart: number, 
    inorderEnd: number
  ): TreeNode | null => {

    // 递归终止条件：当前范围无节点（起始索引>结束索引），返回null
    if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
      return null;
    }

    // 2. 确定当前范围的根节点（先序序列的第一个元素）
    const rootVal = preorder[preorderStart];
    const root = new TreeNode(rootVal); // 创建根节点

    // 3. 找到根节点在中序序列中的索引，用于划分左右子树
    const inorderIndex = map.get(rootVal)!; // ！表示非null断言（确保能找到索引）
    const leftSize = inorderIndex - inorderStart; // 左子树的节点数

    // 4. 递归构造左子树
    // 左子树先序范围：preorderStart+1 ~ preorderStart+leftSize（根节点后leftSize个元素）
    // 左子树中序范围：inorderStart ~ inorderIndex-1（根节点左侧元素）
    root.left = helper(
      preorderStart + 1, 
      preorderStart + leftSize, 
      inorderStart, 
      inorderIndex - 1
    );

    // 5. 递归构造右子树
    // 右子树先序范围：preorderStart+leftSize+1 ~ preorderEnd（左子树之后的剩余元素）
    // 右子树中序范围：inorderIndex+1 ~ inorderEnd（根节点右侧元素）
    root.right = helper(
      preorderStart + leftSize + 1, 
      preorderEnd, 
      inorderIndex + 1, 
      inorderEnd
    );

    return root; // 返回当前范围的根节点
  }

  // 初始调用递归函数，范围是整个先序和中序序列
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

四、代码关键细节解析

1. 递归终止条件

当 preorderStart > preorderEnd 或 inorderStart > inorderEnd 时，说明当前范围内没有节点，返回 null（比如叶子节点的左右子节点，就会触发这个条件）。

2. 左子树节点数的计算

leftSize = inorderIndex - inorderStart，这个计算是划分先序序列的关键——因为先序序列中，根节点之后的 leftSize 个元素，必然是左子树的先序序列，剩下的就是右子树的先序序列。

3. 哈希表的非null断言

代码中 map.get(rootVal)! 用到了 TypeScript 的非null断言（!），原因是题目保证了 preorder 和 inorder 是同一棵二叉树的遍历序列，因此根节点的值一定能在中序序列中找到，不会返回 null。

4. 时间和空间复杂度

• 时间复杂度：O(n)，n 是节点总数。哈希表构建需要 O(n) 时间，递归过程中每个节点被处理一次，每次查找根节点索引是 O(1)；

• 空间复杂度：O(n)，哈希表存储 n 个元素，递归调用栈的深度最坏情况下是 O(n)（比如斜树），最好情况下是 O(log n)（平衡二叉树）。

五、常见易错点提醒

1. 先序序列的划分错误：容易把右子树的先序起始索引算错，记住是 preorderStart + leftSize + 1（跳过根节点和左子树）；

2. 中序序列的边界错误：左子树的中序结束索引是 inorderIndex - 1，右子树的中序起始索引是 inorderIndex + 1，容易漏写 ±1 导致死循环；

3. 忽略空数组情况：当 preorder 和 inorder 为空时，直接返回 null（递归终止条件会处理，但需注意初始调用时的边界）；

4. 不用哈希表优化：直接遍历中序序列找根节点，会导致时间复杂度飙升，在 n 较大时（比如 10^4 级别）会超时。

六、总结

LeetCode 105 题的核心是「利用遍历序列的特性 + 递归分治 + 哈希表优化」，解题的关键在于抓住“先序定根、中序分左右”的规律，再通过递归逐步构造子树。

这道题不仅能帮我们巩固二叉树的遍历知识，还能锻炼递归思维——递归的本质就是“把大问题拆成小问题，解决小问题后拼接结果”，这里的大问题是“构造整个二叉树”，小问题是“构造左子树”和“构造右子树”。

如果能吃透这道题，再遇到“从中序与后序遍历构造二叉树”（LeetCode 106 题）就会事半功倍，因为思路完全相通，只是根节点的位置和序列划分方式略有不同。

在二叉树的算法题中，“根据遍历序列构造二叉树”是高频考点，而 LeetCode 106 题（从中序与后序遍历序列构造二叉树）更是经典中的经典。它不仅考察对二叉树遍历规则的理解，还需要运用分治思想拆解问题，新手容易在“区间划分”上栽坑。今天就带大家一步步拆解这道题，从思路分析到代码实现，再到细节避坑，彻底搞懂如何通过两个遍历序列还原二叉树。

一、题目核心认知

先明确题目要求，避免理解偏差：

• 给定两个整数数组 inorder（中序遍历）和 postorder（后序遍历），二者对应同一棵二叉树；

• 构造并返回这棵二叉树的根节点；

• 默认输入有效（无重复元素，且两个数组长度一致，能构成合法二叉树）。

关键前提：二叉树遍历规则回顾

要解决这道题，必须牢记中序和后序遍历的核心特点（这是解题的灵魂）：

1. 中序遍历（左-根-右）：先遍历左子树，再访问根节点，最后遍历右子树；

2. 后序遍历（左-右-根）：先遍历左子树，再遍历右子树，最后访问根节点。

核心突破口：后序遍历的最后一个元素，一定是当前二叉树的根节点；而中序遍历中，根节点左侧的所有元素都是左子树的节点，右侧的所有元素都是右子树的节点。

二、解题思路拆解（分治思想）

既然能通过后序找到根节点，通过中序划分左右子树，那我们就可以用「分治」的思路，把大问题拆成小问题，递归求解：

步骤1：找到根节点

取 postorder 的最后一个元素，作为当前二叉树的根节点（root）。

步骤2：划分中序遍历的左右子树区间

在inorder 中找到根节点的索引（记为 rootIndex），则：

• 左子树的中序区间：[inorderStart, rootIndex - 1]（根节点左侧所有元素）；

• 右子树的中序区间：[rootIndex + 1, inorderEnd]（根节点右侧所有元素）。

步骤3：划分后序遍历的左右子树区间

后序遍历的区间长度和中序遍历一致（因为对应同一棵子树），设左子树的节点个数为 leftSize = rootIndex - inorderStart，则：

• 左子树的后序区间：[postorderStart, postorderStart + leftSize - 1]（左子树节点个数为 leftSize）；

• 右子树的后序区间：[postorderStart + leftSize, postorderEnd - 1]（去掉最后一个根节点，剩余部分前半为左子树，后半为右子树）。

步骤4：递归构造左右子树

用同样的方法，递归构造左子树和右子树，分别赋值给根节点的 left 和 right 指针。

步骤5：优化索引查询（避免重复遍历）

如果每次在中序数组中找根节点索引都用遍历的方式，时间复杂度会很高（O(n²)）。我们可以提前用一个哈希表（Map），存储中序数组中「元素-索引」的映射，这样每次查询根节点索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

结合上面的思路，我们来实现代码（题目已给出 TreeNode 类，直接复用即可）：

/**
 * Definition for a binary tree node.
 * 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===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

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 === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  // 提前存储中序遍历的「元素-索引」映射，优化查询效率
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  // 递归辅助函数：根据区间构造子树
  // inorderStart/inorderEnd：当前子树在中序数组中的区间
  // postorderStart/postorderEnd：当前子树在后序数组中的区间
  const helper = (inorderStart: number, inorderEnd: number, postorderStart: number, postorderEnd: number): TreeNode | null => {
    // 递归终止条件：区间不合法（没有节点），返回null
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
      return null;
    }

    // 1. 找到当前子树的根节点（后序数组的最后一个元素）
    const rootVal = postorder[postorderEnd];
    const root = new TreeNode(rootVal);

    // 2. 找到根节点在中序数组中的索引，划分左右子树区间
    const rootIndex = map.get(rootVal)!; // 题目保证输入有效，非null

    // 3. 计算左子树的节点个数，用于划分后序数组区间
    const leftSize = rootIndex - inorderStart;

    // 4. 递归构造左子树和右子树，赋值给根节点
    // 左子树：中序[start, rootIndex-1]，后序[start, start+leftSize-1]
    root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
    // 右子树：中序[rootIndex+1, end]，后序[start+leftSize, end-1]
    root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

    // 返回当前子树的根节点
    return root;
  }

  // 初始调用：区间为两个数组的完整区间
  return helper(0, inorder.length - 1, 0, postorder.length - 1);
};

四、代码逐行解析（重点+避坑）

很多新手能看懂思路，但写代码时容易在「区间边界」上出错，这里逐行拆解关键部分，帮大家避坑：

1. 哈希表初始化

const map = new Map<number, number>();
inorder.forEach((val, index) => {
  map.set(val, index);
});

作用：提前缓存中序数组的元素和对应索引，后续每次找根节点索引都能直接通过 map.get(rootVal) 获取，避免重复遍历中序数组，降低时间复杂度。

2. 递归辅助函数（helper）

为什么需要辅助函数？因为我们需要通过「区间边界」来划分左右子树，而主函数的参数只有两个数组，无法直接传递区间信息，所以用 helper 函数封装区间参数，实现递归。

3. 递归终止条件

if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
  return null;
}

避坑点：当区间的起始索引大于结束索引时，说明当前区间没有节点，直接返回 null（比如左子树为空或右子树为空的情况）。比如，根节点的左子树如果没有节点，那么 inorderStart 会等于 rootIndex，此时 inorderStart > rootIndex - 1，触发终止条件，返回 null，正好对应 root.left = null。

4. 根节点创建

const rootVal = postorder[postorderEnd];
const root = new TreeNode(rootVal);

核心：后序遍历的最后一个元素就是当前子树的根节点，这是整个解题的突破口，必须牢记。

5. 区间划分（最容易出错的地方）

const leftSize = rootIndex - inorderStart;
// 左子树递归调用
root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
// 右子树递归调用
root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

避坑解析：

• leftSize 是左子树的节点个数，由「根节点索引 - 中序起始索引」得到，因为中序左子树区间是 [inorderStart, rootIndex - 1]，长度为 rootIndex - inorderStart；

• 后序左子树区间的结束索引 = 起始索引 + 左子树节点个数 - 1（因为区间是闭区间，比如起始索引0，个数2，区间是[0,1]）；

• 后序右子树的起始索引 = 左子树结束索引 + 1，结束索引 = 原后序结束索引 - 1（去掉根节点）；

• 中序右子树区间直接从 rootIndex + 1 开始，到 inorderEnd 结束即可。

五、复杂度分析

• 时间复杂度：O(n)，n 是二叉树的节点个数。哈希表初始化遍历一次中序数组（O(n)），每个节点被递归处理一次（O(n)），每次索引查询 O(1)；

• 空间复杂度：O(n)，哈希表存储 n 个元素（O(n)），递归调用栈的深度最坏情况下为 n（比如二叉树退化为链表），整体空间复杂度 O(n)。

六、总结与拓展

核心总结

这道题的本质是「利用遍历序列的特点找根节点 + 分治思想拆分左右子树」，关键在于两点：

1. 牢记后序最后一个元素是根，中序根节点划分左右子树；

2. 精准划分两个数组的左右子树区间，避免边界出错（建议多动手画示例，标注区间）。

拓展思考

这道题和 LeetCode 105 题（从前序与中序遍历序列构造二叉树）思路高度一致，只是根节点的位置和区间划分略有不同：

• 105题（前序+中序）：前序的第一个元素是根节点；

• 106题（后序+中序）：后序的最后一个元素是根节点。

掌握这两道题，就能轻松应对「遍历序列构造二叉树」的所有同类题型。

进度（90 /188）

其中标记 ※ 的是我认为比较难或者涉及新知识点的题目

刷题也许没有什么意义，但是喜欢一个人思考一整天的灵光一现，也喜欢看到新奇的答案时的恍然大悟，仅此而已。

42. Medium - 1130 - ReplaceKeys ※

实现一个类型 ReplaceKeys，用于替换联合类型中的键，如果某个类型不包含该键则跳过替换。该类型接受三个参数。

一开始我只是想这么写，我想分布式条件类型 + Pick + Omit 来实现。

type ReplaceKeys<U, T, Y> = U extends any 
 ? Omit<U, T & keyof U> & Pick<Y, T & keyof U & keyof Y>
 : any

理论上 case1 是能通过的，但是一直报错。然后我又试了一下，看来判断的 Equal 不认为这两种是相等的：

type T1 = { a: number }
type T2 = { b: number }
type E = Equal<T1 & T2, { a: number, b: number }> // false

不过还是有办法的，我们可以通过一层映射把交叉类型拍平：

type IntersectionToObj<T> = {
  [K in keyof T]: T[K]
}
type E1 = Equal<IntersectionToObj<T1 & T2>, { a: number, b: number }> // true

不过我试了下第二个 case 还是不太好实现，那就直接用映射类型来解决。

利用分布式特性处理联合元素，然后遍历 U 的属性然后按要求进行处理即可。

type ReplaceKeys<U, T, Y> = U extends any
  ? {
    [K in keyof U]: K extends T ? (K extends keyof Y ? Y[K] : never) : U[K]
  }
  : never // 不会进入这个分支

但是看到别人的答案我又开始困惑了：

type ReplaceKeys<U, T, Y> = {
  [K in keyof U]: K extends T ? (K extends keyof Y ? Y[K] : never) : U[K]
}

查了半天只有这个 pr ，官方文档里也没有明确说明。

形如 { [P in keyof T]: X } 的映射类型（其中 T 是类型参数）被称为 isomorphic mapped type（同构映射类型），因为它会产生一个与 T 具有相同结构的类型。通过此 PR，我们使同构映射类型的实例化在联合类型上具有分布性。

43. Medium - 1367 - Remove Index Signature 移除索引签名 ※

实现 RemoveIndexSignature<T>，移除一个对象类型的索引签名。

索引签名（Index Signature） 是 TypeScript 中用于描述对象中未明确声明的属性的类型。它允许你定义一个对象可以有任意数量的属性，只要这些属性的键和值符合指定的类型。

interface StringDictionary {
  [key: string]: string;  // 索引签名
  // 表示该对象可以有任意多个属性，键必须是 string 类型，值也必须是 string 类型。
}

和索引签名对应的是具体属性，这两种也可以混合使用，但是具体属性的类型必须是索引签名类型的子类型：

interface MixedType {
  // 具体属性
  name: string;
  age: number;
  // 索引签名
  [key: string]: string | number;  // 必须包含具体属性的类型
}

要处理这个问题，就要针对索引签名的特点，他是一个宽泛的类型（string/number/symbol），而具体属性是一个字面量类型，比如 "name" ，我们依次判断它是否为 string，number 或 symbol 都不是则证明是具体属性，否则为索引签名。

type RemoveIndexSignature<T> = {
  [K in keyof T as
  string extends K 
    ? never
    : number extends K 
      ? never
      : symbol extends K 
        ? never
        : K
  ]: T[K]
}`

在评论区看到一个很天才的解法

type RemoveIndexSignature<T, P = PropertyKey> = {
  [K in keyof T as P extends K? never : K extends P ? K : never]: T[K]
}

其中 PropertyKey 上是 TypeScript 的内置类型 type PropertyKey = string | number | symbol;。它的判断过程如下：

P extends K ? never : (K extends P ? K : never)  /* P = string | number | symbol */

// becomes
(string | number | symbol) extends K ? never : (K extends P ? K : never)

// becomes
| string extends K ? never : (K extends string ? K : never)
| number extends K ? never : (K extends number ? K : never)
| symbol extends K ? never : (K extends symbol ? K : never)

本质上和我们上面的写法是一样的，但是利用条件类型的分布性，一下子判断了三种类型。୧(๑•̀◡•́๑)૭

44. Medium - 1978 - Percentage Parser 百分比解析器

实现类型 PercentageParser。根据规则 /^(\+|\-)?(\d*)?(\%)?$/ 匹配类型 T。

匹配的结果由三部分组成，分别是：[正负号, 数字, 单位]，如果没有匹配，则默认是空字符串。

type Sign = '+' | '-'
type PercentageParser<A extends string> =
  A extends `${infer F}%`
  /** 存在 % */
    ? F extends `${infer S extends Sign}${infer N}`
      ? [S, N, '%']
      : ['', F, '%']
  /** 不存在 % */
    : A extends `${infer S extends Sign}${infer N}`
      ? [S, N, '']
      : ['', A, '']

题目不难，加几个分支判断就可以了。或者这样写优雅一点（大概）：

type SignParser<A extends string> = A extends `${infer S extends '+' | '-'}${infer N}` ? [S, N] : ['', A]
type PercentageParser<A extends string> = A extends `${infer F}%` ? [...SignParser<F>, '%'] : [...SignParser<A>, '']

45. Medium - 2070 - Drop Char 删除字符

从字符串中剔除指定字符。

type DropChar<S, C> = S extends `${infer F}${infer R}`
  ? F extends C 
    ? DropChar<R, C>
    : `${F}${DropChar<R, C>}`
  : ''

没有新的知识点，简单题。

46. Medium - 2257 - MinusOne 减一 ※

给定一个正整数作为类型的参数，要求返回的类型是该数字减 1。

有点意思的一道题目，没有新的知识点，但是类似于算法中的模拟题。需要递归加不同情况的判断，复杂度较高。

我先想到了一个比较搞的办法，生成长度为 T 的数组，然后移除一个元素，再获取数组长度。

type MakeArray<T extends number, R extends any[] = []> =
  R['length'] extends T ? R : MakeArray<T, [...R, any]>
type MinusOne<T extends number> = 
  MakeArray<T> extends [infer _F, ...infer R] ? R['length'] : never

1000 以内是可行的，但是再大就会出现错误：

type A = MakeArray<1101> // error: 类型实例化过深，且可能无限。ts(2589)

那么只能换一种方法，通过模拟减法的方式实现，枚举最后一位即可，如果最后一位大于 0 则只需要操作最后一位，否则需要递归处理：

type MinusOne2String<T extends string> =
  T extends `${infer F}0` // 如果最后一位是0，则把此位改为9，然后递归处理（题目限定了是正数）
  ? `${MinusOne2String<F>}9`
  : T extends `${infer F}9` // 其他情况直接把最后一位减一
  ? `${F}8`
  : T extends `${infer F}8`
  ? `${F}7`
  : T extends `${infer F}7`
  ? `${F}6`
  : T extends `${infer F}6`
  ? `${F}5`
  : T extends `${infer F}5`
  ? `${F}4`
  : T extends `${infer F}4`
  ? `${F}3`
  : T extends `${infer F}3`
  ? `${F}2`
  : T extends `${infer F}2`
  ? `${F}1`
  : T extends `${infer F}1`
  ? `${F}0`
  : '0'
// 100-1=099 这种情况需要删除前导零
type removeLeadZero<T extends string> = 
  T extends '0' ? '0' : T extends `0${infer R}` ? removeLeadZero<R> : T 
// 删除前导零后，转换为数字类型
type MinusOne<T extends number> = 
  removeLeadZero<MinusOne2String<`${T}`>> extends `${infer X extends number}` ? X : 0

47. Medium - 2595 - PickByType

从 T 中选择可赋值给 U 的属性类型集合。

type PickByType<T, U> = {
  [K in keyof T as T[K] extends U ? K : never ]: T[K]
}

送分题，知识点前面的题目都有涉及。

48. Medium - 2688 - StartsWith

实现 StartsWith<T, U>,接收两个 string 类型参数,然后判断 T 是否以 U 开头,根据结果返回 true 或 false。

type StartsWith<T extends string, U extends string> =
  T extends `${U}${infer F}` ? true : false

送分题+1，模板字符串类型基础。

49. Medium - 2693 - EndsWith

实现 EndsWith<T, U>,接收两个 string 类型参数,然后判断 T 是否以 U 结尾,根据结果返回 true 或 false。

type EndsWith<T extends string, U extends string> =
  T extends `${string}${U}` ? true : false

50. Medium - 2757 - PartialByKeys

实现一个通用的 PartialByKeys<T, K>，它接收两个类型参数 T 和 K。

K 指定应设置为可选的 T 的属性集。当没有提供 K 时，它就和普通的 Partial<T> 一样使所有属性都是可选的。

前面已经讲过 IntersectionToObj 这个小技巧，这里就比较简单了，其中 Partial 是内置的工具类型，可以把一个对象类型的全部属性都变成可选。

type IntersectionToObj<T> = {
  [K in keyof T]: T[K]
}

type PartialByKeys<T , K extends keyof T = keyof T> = 
  IntersectionToObj< Omit<T, K> & Partial<Pick<T, K>> >

51. Medium - 2759 - RequiredByKeys

实现一个通用的 RequiredByKeys<T, K>，它接收两个类型参数 T 和 K。

K 指定应设为必选的 T 的属性集。当没有提供 K 时，它就和普通的 Required<T> 一样使所有的属性成为必选的。

和 PartialByKeys 本质上没有什么区别，Required 也是内置的工具类型，可以把一个对象类型的全部属性，用于将一个类型 T 中的所有属性转换为‌必填属性（即移除其可选性 ?）。

type IntersectionToObj<T> = {
  [K in keyof T]: T[K]
}
type RequiredByKeys<T, K extends keyof T = keyof T> =
  IntersectionToObj<Omit<T, K> & Required<Pick<T, K>>>

52. Medium - 2793 - Mutable ※

实现一个通用的类型 Mutable<T>，使类型 T 的全部属性可变（非只读）。

这题不难，但是涉及到映射类型的一个语法，之前没有涉及过。mapped-types

type Mutable<T extends object> ={
  -readonly [K in keyof T]: T[K]
}

53. Medium - 2852 - OmitByType

从类型 T 中选择不可赋值给 U 的属性成为一个新的类型。

直到了 as 和 Mapped Types 的用法，这也很简单，和之前的 Omit 没什么区别。

type OmitByType<T, U> = {
  [K in keyof T as T[K] extends U ? never : K]: T[K]
}

54. Medium - 2946 - ObjectEntries

实现 Object.entries 的类型版本。

首先这题需要应用分布式条件类型，所以需要先构造一个由类型key组成的联合类型 U 然后 U extends ... 触发分布式。

type ObjectEntries<T, U = keyof T> =
  U extends keyof T ? [U, T[U]] : never

不过有个case 过不去。

type eq = Equal<ObjectEntries<Partial<Model>>, ModelEntries> // false
type o = ObjectEntries<Partial<Model>>
// ["name", string | undefined] | ["age", number | undefined] | ["locations", string[] | null | undefined]

可以看到由于 Partial 导致每个类型都多了一个 undefined。很明显这里需要 Required，但是需要先了解一下它的特性。

type r1 = Required<{ key?: undefined }> // {key: never}
type r2 = Required<{ key: undefined }> // {key: undefined}
type r3 = Required<{ key: string | undefined }> // {key: string | undefined}
type r4 = Required<{ key?: string | undefined }>  // {key:string}

可以看到在存在 ? 时，Required 会删除类型中的 undefined，否则不会。

而此题的要求是：如果类型存在 ? 就删除 undefined，但是如果类型只有 undefined 则不处理。我只能说，题本身不难，但是描述的不清楚，只能看用例。

type ObjectEntries<T, U = keyof T> =
  U extends keyof T 
    ? [U, [T[U]] extends [undefined] ? undefined : Required<T>[U]] 
    : never

55. Medium - 3062 - Shift

实现类型版本的 Array.shift。

type Shift<T extends any[]> = T extends [infer F, ...infer R] ? [...R] : []

infer 的基础应用，在最前面的 First of Array 就了解过了。

56. Medium - 3188 - Tuple to Nested Object

给一个只包含字符串类型的元组 T 和一个类型 U 递归构建一个对象。

type TupleToNestedObject<T extends string[], U> = 
  T extends [infer F extends string, ...infer R extends string[]] 
    ? Record<F, TupleToNestedObject<R, U>> : U

每次提取数组中第一个元素，然后把该元素作为键，递归构造的对象作为值。

57. Medium - 3192 - Reverse

实现类型版本的数组反转 Array.reverse

type Reverse<T extends any[]> = T extends [infer F, ...infer R] 
  ? [...Reverse<R>, F]
  : []

使用递归的方式，每次都把第一个元素移到最后一个。

58. Medium - 3196 - Flip Arguments

实现 lodash 中 _.flip 函数的类型版本。

类型转换函数 FlipArguments<T> 要求函数类型 T，并返回一个新的函数类型，该类型具有与 T 相同的返回类型但参数顺序颠倒。

type FlipArguments<T extends Function> = 
  T extends (...args: infer P) => infer R ? (...args: Reverse<P>) => R : never

通过 infer 获取函数的参数和返回值，并且通过上一题实现的 Reverse 将参数反转。

59. Medium - 3243 - FlattenDepth

递归展开数组至指定深度

首先需要实现一个铺平一次的函数，这个比较简单

type FlattenOnce<A extends any[]> = A extends [infer F, ...infer R]
  ? F extends any[] ? [...F, ...FlattenOnce<R>] : [F, ...FlattenOnce<R>]
  : []

TypeScript 中无法进行数字计算，我们可以通过邪修实现，这点我们在前面的 MinusOne 已经实现，所以这里直接引用 MinusOne 就可以了。

type FlattenDepth<T extends any[], depth extends number = 1> =
  depth extends 0 // 判断深度为零，则已经不需要铺平了
  ? T
  : FlattenOnce<T> extends T // 判断是否铺平前后的结果一致，一致则不需要再处理了
    ? T 
    : FlattenDepth<FlattenOnce<T>, MinusOne<depth>>

当然我们可以用之前在里面用过的用数组记录数字的方法，只不过 TypeScript 中数组长度有限制，当然这一题中是没有问题的，嵌套最多才 5 层

type FlattenDepth<T extends any[], depth = 1, depArr extends any[] = []> = 
  depArr['length'] extends depth
    ? T 
    : FlattenOnce<T> extends T ? T : FlattenDepth<FlattenOnce<T>, depth, [...depArr, any]>

60. Medium - 3326 - BEM style string

使用块（Block）、元素（Element）、修饰符（Modifier）命名（BEM）是 CSS 中类的一种流行命名约定。

例如，块组件表示为 btn，依赖于块的元素表示为 btn__price，更改块样式的修饰符表示为 btn-big 或 btn__prise-warning。

实现 BEM<B，E，M>，从这三个参数生成字符串并集。其中 B 是字符串文字，E 和 M 是字符串数组（可以为空）。

// 把A和B连接，先把B处理为联合类型，然后用S连接
type JoinWithSeparator<A extends string, B extends string[], S extends string, B2Union extends string = B[number]> = 
  B2Union extends any ? `${A}${S}${B2Union}` : never

type BEM<B extends string, E extends string[], M extends string[]> = 
  E['length'] extends 0 // 判断E是否为空
    ? JoinWithSeparator<B, M, '--'> // 如果E为空, B和M连接
    : M['length'] extends 0 // 判断M是否为空
      ? JoinWithSeparator<B, E, '__'> // E不为空，M为空，把B和M连接
      : JoinWithSeparator<JoinWithSeparator<B, E, '__'>, M, '--'> // 都不为空，先把B和E连接，然后再加上M

需要写一个辅助工具类型 JoinWithSeparator 用于连接一个字符和数组，逻辑有点小复杂，已经加了完整注释。

61. Medium - 3376 - InorderTraversal

实现二叉树中序遍历的类型版本。

如果会中序遍历二叉树这题就不难了，不会的可以先学学数据结构。

type InorderTraversal<T extends TreeNode | null> = 
 T extends null 
   ? [] 
   : [...InorderTraversal<T['left']>, T['val'], ...InorderTraversal<T['right']>]

比较麻烦的是，T extends null 语法无法判断第二个分支中 T 不为空，所以可以反过来，判断 T 是否为 TreeNode。

type InorderTraversal<T extends TreeNode | null> =
  T extends TreeNode
  ? [
    ...InorderTraversal<T['left']>,
    T['val'],
    ...InorderTraversal<T['right']>
  ] : []

62. Medium - 4179 - Flip

实现 just-flip-object 的类型版本（把类型的键和值类型反转）。

type Flip<T> = {
  [K in keyof T as T[K] extends number | string | boolean ? `${T[K]}` : never]: K
}

为了保证 T[K] 类型正确，加了一个 extends number | string | boolean 的限制。

63. Medium - 4182 - Fibonacci Sequence 斐波那契序列 ※

实现一个通用的 Fibonacci<T>，它接受一个数字 T 并返回其相应的斐波纳契数。

序列开始：1、1、2、3、5、8、13、21、34、55、89、144...

首先斐波纳契公式 f(n)=f(n-1)+f(n-2) 可以递归实现。由于 TypeScript 类型无法使用加法，所以我们通过数组的元素个数来变向进行计算，至于减法可以复用之前实现的 MinusOne。

type FibonacciArray<T extends number, A extends any[] = []> =
    T extends 1
    ? [any]
    : T extends 2
      ? [any]
      : [...FibonacciArray<MinusOne<MinusOne<T>>>, ...FibonacciArray<MinusOne<T>>]
type Fibonacci<T extends number> = FibonacciArray<T>['length']

看了下别人的答案，优化空间还是很大的，下面是正向计算，Index 表示计算到了第 n 个数字，Cur 表示 f(n)，Prev 表示 f(n-1)

type Fibonacci<
  T extends number,
  Index extends any[] = [any, any],
  Cur extends any[] = [any],
  Prev extends any[] = [any]
> =
  T extends 1 | 2
    ? 1
    : Index['length'] extends T
      ? Cur['length']
      : Fibonacci<T, [...Index, any], [...Cur, ...Prev], Cur>

64. Medium - 4260 - AllCombinations ※

实现 AllCombinations<S> 类型，该类型返回使用 S 中的字符所组成的所有字符串，每个字符最多使用一次。

type AllCombinations<S extends string, P extends string = ''> =
  S extends `${infer F}${infer R}` 
    ? '' | F | `${F}${AllCombinations<`${R}${P}`>}` // S[0] 开头的所有排列情况
      | AllCombinations<R, `${P}${F}`> // 除了 S[0] 开头以外的所有情况
    : ''

很有意思的题目，实现一个字符串中字符的所有组合。我的解法是 AllCombinations<S, P> 表示获取字符串 ${S}${P} 中，以 S 每个字母开头的全排列组合。

所以 AllCombinations<S, ''> 就是答案，而它等于 S[0] 为开头的所有情况，再加上 AllCombinations<S.split(1), S[0]>（伪代码示例）

而 S[0] 为开头的所有情况，就是求 S[0] 连接剩余字符的全排列，也就是 AllCombinations<S.split(1), ''>

65. Medium - 4425 - Greater Than

在本次挑战中，你需要实现一个类似 T > U 的类型： GreaterThan<T, U> 负数无需考虑。

这种题我可以说不难，就是有点恶心。我不喜欢！下面的代码我加了注释，应该可以看懂。

type LengthOfString<S extends string> = Split<S>['length'];
type FirstOfString<S extends string> = S extends `${infer F}${infer R}`
  ? F
  : never;
type RestOfString<S extends string> = S extends `${infer F}${infer R}`
  ? R
  : never;

type Split<S extends string> = S extends `${infer F}${infer R}`
  ? [F, ...Split<R>]
  : [];

// 比较10以内数字的大小
type GreaterThanDigit<
  T extends string,
  U extends string,
  D extends string = '9876543210'
> = D extends `${infer F}${infer R}` // 从大到小依次比较每一个数字
  ? F extends U // 如果先匹配了U 则证明T≤U 返回false
    ? false
    : F extends T // 如果先匹配了T 则证明T>U 返回true
      ? true
      : GreaterThanDigit<T, U, R> // 再尝试匹配下一个数字
  : false;

type GreaterThanString<
  T extends string,
  U extends string,
  LEN_T extends number = LengthOfString<`${T}`>, // T的长度
  LEN_U extends number = LengthOfString<`${U}`>, // U的长度
  FIRST_T extends string = FirstOfString<`${T}`>, // T的长度
  FIRST_U extends string = FirstOfString<`${U}`> // U的长度
> = LEN_U extends LEN_T // 判断长度是否相同
  ? LEN_T extends 1 // 判断相同，长度是否为1
    ? GreaterThanDigit<FIRST_T, FIRST_U> // 长度为1 直接比较首位
    : FIRST_T extends FIRST_U // 长度相同，且长度不为1，依次比较每一位，先判断首位
      ? GreaterThanString<RestOfString<`${T}`>, RestOfString<`${U}`>> // 首位相同 则比较下一位
      : GreaterThanDigit<FIRST_T, FIRST_U> // 首位不同，则比较大小
  : GreaterThan<LEN_T, LEN_U>; // 如果长度不相同，则长度大的数字更大

type GreaterThan<T extends number, U extends number> = GreaterThanString<
  `${T}`,
  `${U}`
>;

66. Medium - 4471 - Zip

在这个挑战中，你需要实现一个类型 Zip<T, U>，其中 T 和 U 必须是元组。

就是把所有元组中的第1项组成结果中的第1项，所有元组中的第2项组成结果中的第2项....所有元组中的第n项组成结果中的第n项，比较简单。

type Zip<T extends any[], U extends any[]> = T extends [infer TF, ...infer TR]
  ? U extends [infer UF, ...infer UR]
    ? [[TF, UF], ...Zip<TR, UR>]
    : []
  : [];

67. Medium - 4484 - IsTuple ※

实现类型 IsTuple, 传入类型 T 并返回类型 T 是否为一个元组类型。

A tuple type is another sort of Array type that knows exactly how many elements it contains, and exactly which types it contains at specific positions.

元组类型 是另一种“数组”类型，它确切地知道它包含多少元素，以及它在特定位置包含哪些类型。

T extends readonly any[] 判断 T 为数组和元素，添加 readonly 可以兼容 readonly [1] 这种情况。

根据定义可以知道，元组类型的长度是固定的，所以 Tuple['length'] 是一个具体的数字，而数组 A['length'] 是 number。

因此，可以通过 number extends T['length'] 来判断 T 是否为元组而不是数组。

type IsTuple<T> = [T] extends [never]
  ? false
  : T extends readonly any[]
    ? number extends T['length']
      ? false
      : true
    : false;

68. Medium - 4499 - Chunk

你知道 lodash 吗？Chunk 是其中一个非常有用的函数，现在让我们实现它。Chunk<T，N> 接受两个必需的类型参数，T 必须是元组，N 必须是大于等于 1 的整数。

type Chunk<
  T extends any[],
  N extends number,
  Result extends any[] = [],
  Current extends any[] = []
> = T extends [infer F, ...infer R] // 判断是否还有元素
  ? Current['length'] extends N // 有元素，判断当前的块已经满了
    ? Chunk<R, N, [...Result, Current], [F]> // 如果当前的块已经满了，把它放进结果数组里
    : Chunk<R, N, Result, [...Current, F]> // 没有满，就把元素放进当前块
  : Current['length'] extends 0 // T中所有元素都处理完了，判断当前块中是否有元素
    ? Result // 当前块为空的，直接返回结果
    : [...Result, Current]; // 否则把当前块放进结果，再返回

69. Medium - 4518 - Fill

Fill 是一个通用的 JavaScript 函数，现在来实现它的类型版本。Fill<T, N, Start?, End?> 接受 4 个参数, T 是一个元组，N 是任意类型， Start and End 是大于等于 0 的整数。把 T 在 [Start.End] 范围内的元素都替换为 N。

type Fill<
  T extends unknown[], // 原数组
  N, // 要填充的类型
  Start extends number = 0, // 开始下标
  End extends number = T['length'], // 结束下标
  Result extends unknown [] = [], // 结果数组
  In extends boolean = false // 是否在[Start,End]范围内
> = T extends [infer F, ...infer R] // T是否存在第一个元素
  ? Result['length'] extends End // 先判断是否为结束下标
    ? Fill<R, N, Start, End, [...Result, F], false>  // 是结束下标，则证明已经填充完了，后面填充T的内容就行
    : Result['length'] extends Start // 不是，判断是否为开始下标
      ? Fill<R, N, Start, End, [...Result, N], true>  // 是开始下标，则填充N，用IN=true表示已经在范围内
      : In extends true // 判断是否在[Start,End]范围内
        ? Fill<R, N, Start, End, [...Result, N], true> // 如果在范围内 则用N填充
        : Fill<R, N, Start, End, [...Result, F], false> // 不在范围内 用T中内容填充
  : Result // 处理完成，返回结果

70. Medium - 4803 - Trim Right

实现 TrimRight<T>，它接收确定的字符串类型并返回一个新的字符串，其中新返回的字符串删除了原字符串结尾的空白字符串。

type TrimRight<S extends string> =
  S extends `${infer F}${' '|'\n'|'\t'}` ? TrimRight<F> : S

71. Medium - 5117 - Without

实现一个像 Lodash.without 函数一样的泛型 Without<T, U>，它接收数组类型的 T 和数字或数组类型的 U 为参数，会返回一个去除 U 中元素的数组 T。

Equal 是玄学，别问，用就完事了。

type Includes<T extends readonly unknown[], U> = 
  T extends [infer F, ...infer Rest]
    ? Equal<F, U> extends true ? true : Includes<Rest, U>
    : false;

type Without<T extends any[], U extends any> = T extends [infer F, ...infer R]
  ? U extends any[]
    ? Includes<U, F> extends true // 如果U是数组类型，使用Includes判断是否包含
      ? Without<R, U>
      : [F, ...Without<R, U>]
    : F extends U // 如果U不是数组，直接判断
      ? Without<R, U>
      : [F, ...Without<R, U>]
  : []

评论区看到了更好的解法，先转成联合在判断是否包含

type ToUnion<T extends any> = T extends any[] ? T[number] : T;

type Without<T extends any[], U extends any> = 
T extends [infer F, ...infer R]
  ? F extends ToUnion<U>
    ? Without<R, U>
    : [F, ...Without<R, U>]
  : [];

72. Medium - 5140 - Without

实现 Math.trunc 的类型版本，它接受字符串或数字，并通过删除所有小数来返回数字的整数部分。

简单的模板字符串模式匹配，注意 '-.3' 这种删除小数点后面的内容后需要手动补 0。

type Trunc<T extends number | string> =
  `${T}` extends `${infer F}.${infer _}`
    ? F extends '-' | ''
      ? `${F}0`
      : F
    : `${T}`;

73. Medium - 5153 - IndexOf

实现类型版本的 Array.indexOf，indexOf<T, U> 接受两个参数，数组 T 和任意类型 U 返回 U 在 T 中第一次出现的下标，不存在返回 -1。

type IndexOf<T extends any[], U, Pre extends any[] = []> =
  T extends [infer F, ...infer R]
    ? Equal<F, U> extends true
      ? Pre['length']
      : IndexOf<R, U, [...Pre, F]>
    : -1

因为 TypeScript 无法进行计算，所以思路还是一样，用一个数组 Pre 记录已经遍历了几个数字，用 Pre['length'] 计数。

74. Medium - 5310 - Join

实现类型版本的 Array.join，Join<T, U>接受一个数组 T 字符串或数字类型 U，返回 T 中的所有元素用 U 连接的字符串，U 默认为 ','。

type Join<
  T extends any[],
  U extends string | number = ',',
  Pre extends string = ''
> = T extends [infer F, ...infer R]
  ? Pre extends ''
    ? Join<R, U, `${F & string}`>
    : Join<R, U, `${Pre}${U}${F & string}`>
  : Pre;

其中 F & string 因为 F 的类型是 any 但是只有一部分类型可以反正模板字符串中，所以这里类型会把报错，通过 & string 限制为 string。

75. Medium - 5317 - LastIndexOf

实现类型版本的 Array.lastIndexOf, LastIndexOf<T, U> 接受数组 T, any 类型的 U, 如果 U 存在于 T 中, 返回 U 在数组 T 中最后一个位置的索引, 不存在则返回 -1

type LastIndexOf<
  T extends any[],
  U,
  Pre extends any[] = [],
  Result extends number = -1
> = T extends [infer F, ...infer R]
? Equal<F, U> extends true // 判断当前的值是否为U
  ? LastIndexOf<R, U, [...Pre, F], Pre['length']> // 如果是，更新Result，然后继续处理
  : LastIndexOf<R, U, [...Pre, F], Result>
: Result

76. Medium - 5360 - Unique 数组去重

实现类型版本的 Lodash.uniq 方法，Unique 接收数组类型 T, 返回去重后的数组类型。

type Includes<T extends readonly unknown[], U> = 
  T extends [infer F, ...infer Rest]
    ? Equal<F, U> extends true ? true : Includes<Rest, U>
    : false;

type Unique<
  T extends any[],
  Result extends any[] = [],
> = T extends [infer F, ...infer R]
  ? Includes<Result, F> extends true
    ? Unique<R, Result>
    : Unique<R, [...Result, F]>
  : Result;

顺便评论区看到另一个，算是利用分布式条件类型更简洁的实现了 Includes 。

type Unique<T, U = never> =
  T extends [infer F, ...infer R]
    ? true extends (U extends U ? Equal<U, [F]> : never)
      ? Unique<R, U>
      : [F, ...Unique<R, U | [F]>]
    : []

77. Medium - 5821 - MapTypes 映射类型

实现 MapTypes<T, R>，把对象 T 中的类型根据 R 做转换。比如 R 为 { mapFrom: string, mapTo: boolean } 表示把 T 中的所有 string 类型改为 boolean。

// 根据类型映射的定义 和 原类型 获取映射后的类型
type getType<T extends { mapFrom: any; mapTo: any }, P> = T extends any
  ? T['mapFrom'] extends P // 利用分布式条件类型，依次判断是否匹配mapFrom类型
    ? T['mapTo'] // 符合的返回对应的mapTo类型
    : never // 不符合返回never 其他类型和never联合只会剩下其他类型
  : never;

type MapTypes<T, R extends { mapFrom: any; mapTo: any }> = {
  // { mapFrom: T[K]; mapTo: any } 是否可以赋值给R
  [K in keyof T]: { mapFrom: T[K]; mapTo: any } extends R
    ? getType<R, T[K]> // 证明他的类型匹配了mapFrom 需要返回对应的mapTo
    : T[K]; // 否则不需要调整
};

78. Medium - 7544 - Construct Tuple 构造元组 ※

构造一个给定长度的元组。

这题简直太水了，递归就可以 TypeScript 最多递归到999层，所以最后一个 case Expect<Equal<ConstructTuple<1000>['length'], 1000>> 会失败。

// 生成元组，但是TS递归只能到999
type ConstructTuple<
  N extends string | number,
  Result extends any[] = []
> = `${Result['length']}` extends `${N}`
  ? Result
  : ConstructTuple<N, [...Result, unknown]>;

但是，让 9999 成功才是有趣的问题，我开始一直想二分，把自己困住了，后来发现简单的按位计算就可以。参考github.com/type-challe…

// 生成元组，但是TS递归只能到999
type ConstructTupleSimple<
  N extends string | number,
  Result extends any[] = []
> = `${Result['length']}` extends `${N}`
  ? Result
  : ConstructTupleSimple<N, [...Result, unknown]>;

// 把数组T中的元素数量*10
type Multi10<T extends any[]> = [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T]

// 从左到右依次计算 例321 = (3*10+2)*10+1
type ConstructTuple<
  L extends number | string,
  Result extends any[] = []
> = `${L}` extends `${infer F}${infer R}`
  ? ConstructTuple<R, [...Multi10<Result>, ...ConstructTupleSimple<F>]>
  : Result;

79. Medium - 8640 - Number Range

构造指定范围内所有数字的联合。

好像在前面做过类似的题目……通过 Arr 辅助记录遍历数字，Result 记录结果，InRange 记录是否在范围内。

type NumberRange<L, H, Arr extends any[] = [], Result = never, InRange = false> =
  Arr['length'] extends L
    ? NumberRange<L, H, [...Arr, unknown], L | Result, true>
    : Arr['length'] extends H
      ? Result | H
      : InRange extends true
        ? NumberRange<L, H, [...Arr, unknown], Arr['length'] | Result, InRange>
        : NumberRange<L, H, [...Arr, unknown], Result, InRange>

也有更直观的解法：

type ConstructUnion<
  N extends string | number,
  Result extends any[] = []
> = `${Result['length']}` extends `${N}`
  ? Result[number]
  : ConstructUnion<N, [...Result, Result['length']]>;

type NumberRange<L extends number, H extends number> =
  | Exclude<ConstructUnion<H>, ConstructUnion<L>>
  | L
  | H;

80. Medium - 8767 - Combination ※

给定一个字符串数组，执行排列和组合。

// 计算T中每个元素开头的 T和P中所有元素组成的全部组合
type Combination<T extends string[], P extends string[] = []> =
  T extends [infer F extends string, ...infer R extends string[]] // 先计算F开头的所有情况
    ? `${F} ${Combination<[...R, ...P]>}` // 首个单词是F 然后连接 其他单词的全排列
        //（在模板字符串中的联合类型会自动生成所有情况的模板字符串结果的联合）
      | Combination<R, [...P, F]> // 继续计算单个单词剩余单词的情况
      | F // 单个单词
    : never

这种题我每次都要花一个小时做出来，头痛。看了下别人的解法很nb，利用联合类型分布式遍历 T，少了一次递归。

type Combination<T extends string[], All = T[number], Item = All>
  = Item extends string
    ? Item | `${Item} ${Combination<[], Exclude<All, Item>>}`
    : never

81. Medium - 8987 - Subsequence ※

给定一个唯一元素数组，返回所有可能的子序列。

type UnionAddT<U extends any[], T> = U extends any ? [T, ...U] : never
type Subsequence<T extends any[]> = T extends [infer F, ...infer R]
  ? Subsequence<R> // 不包含F的所有子序列
      | UnionAddT<Subsequence<R>, F> // 包含F的所有子序列
  : []

这题不难，加了重点标识因为新学了一个语法：当 ... 展开运算符应用到联合类型时，会对联合类型的每个成员分别展开，然后将结果再组成联合类型。

type Subsequence<T extends unknown[]> = T extends [infer X, ...infer Y]
  ? [X, ...Subsequence<Y>] | Subsequence<Y>
  : [];

82. Medium - 9142 - CheckRepeatedChars

实现类型 CheckRepeatedChars<S> 返回 S 中是否有重复字符。

type CheckRepeatedChars<
  T extends string,
  visited = never
> = T extends `${infer F}${infer R}`
  ? F extends visited
    ? true
    : CheckRepeatedChars<R, visited | F>
  : false;

83. Medium - 9286 - FirstUniqueCharIndex

给一个字符串 S 找到第一个不重复字符的下标，不存在返回 -1。 (灵感来自 leetcode 387)（笑死力扣都来了）

type GetRepectChars<T extends string, Once = never, Repeated = never> = 
  T extends `${infer F}${infer R}`
    ? F extends Once
      ? GetRepectChars<R, Once, Repeated | F>
      : GetRepectChars<R, Once | F, Repeated>
    : Repeated

type FirstUniqueCharIndex<T extends string, Repeated = GetRepectChars<T>, Index extends any[] = []> = 
  T extends `${infer F}${infer R}`
    ? F extends Repeated
      ? FirstUniqueCharIndex<R, Repeated, [...Index, F]>
      : Index['length']
    : -1

84. Medium - 9616 - Parse URL Params

实现类型层面的解析器，把 URL 中的参数字符串解析为一个联合。

type ParseUrlParams<T extends string> = T extends `${infer F}/${infer R}`
  ? F extends `:${infer P}`
    ? P | ParseUrlParams<R>
    : ParseUrlParams<R>
  : T extends `:${infer P}`
    ? P
    : never

85. Medium - 9896 - GetMiddleElement

通过实现一个 GetMiddleElement 方法，获取数组的中间元素，用数组表示

如果数组的长度为奇数，则返回中间一个元素 如果数组的长度为偶数，则返回中间两个元素

type GetMiddleElement<T extends any[]> =
  T['length'] extends 0 | 1 | 2
    ? T
    : T extends [infer _L, ...infer M, infer _R]
      ? GetMiddleElement<M>
      : []

简单，每次删除前后两个元素，对长度为 0 1 2 的数组特殊处理。

86. Medium - 9898 - Appear only once

找出目标数组中只出现过一次的元素。例如：输入 [1,2,2,3,3,4,5,6,6,6]，输出 [1,4,5]。

// 判断联合类型T中是否存在U
type Includes<T, U> = true extends (T extends any ? Equal<T, U> : never)
  ? true
  : false;

type FindEles<
  T extends any[],
  Pre extends any[] = [],
  Res extends any[] = []
> = T extends [infer F, ...infer R]
  ? Includes<[...Pre, ...R][number], F> extends true // 如果F前后组成的数组是否包含F
    ? FindEles<R, [...Pre, F], Res> // 包含F 则证明不唯一 结果不添加F
    : FindEles<R, [...Pre, F], [...Res, F]> // 不包含F 则证明唯一 结果添加F
  : Res; // 遍历结束 返回结果

87. Medium - 9989 - Count Element Number To Object

通过实现一个 CountElementNumberToObject 方法，统计数组中相同元素的个数。

// 把数组拍平，然后把其中never元素删除
type Flatten<A extends any[]> = A extends [infer F, ...infer R] // 判断A存在第一个元素F
  ? [F] extends [never]
    ? [...Flatten<R>]
    : F extends any[]
    ? [...Flatten<F>, ...Flatten<R>]
    : [F, ...Flatten<R>]
  : [];

type CountElementNumberToObject<
  T extends any[],
  // 辅助计数的对象，用数组计数
  Aux extends Record<string | number, any[]> = {},
  // T中有嵌套数组 把T拍平
  F extends (number | string)[] = Flatten<T>
> = F extends [
  infer L extends number | string, // 取第一个元素
  ...infer R extends (number | string)[]
]
  ? CountElementNumberToObject<
      R,
      {
        [K in keyof Aux | L]: K extends L // 遍历Aux中key
          ? L extends keyof Aux // 遍历到L了，判断如果L是Aux中的key
            ? [...Aux[K], unknown] // 就在对应数组中添加一个元素
            : [unknown] // 不在就新创建一个数组，添加一个元素
          : Aux[K]; // 其他key不做处理
      }
    >
  : {
      [K in keyof Aux]: Aux[K]['length']; // 把结果映射为数组的长度
    };

88. Medium - 10969 - Integer ※

请完成类型 Integer<T>，类型 T 继承于 number，如果 T 是一个整数则返回它，否则返回 never。

type OnlyZero<T> = T extends `${infer F}${infer R}`
  ? F extends '0'
    ? OnlyZero<R>
    : false
  : true;
type ToNumber<T> = T extends `${infer N extends number}` ? N : never;
type Integer<T> = T extends number
  ? number extends T
    ? never
    : `${T}` extends `${infer Int}.${infer Deci}`
    ? OnlyZero<Deci> extends true
      ? ToNumber<Int>
      : never
    : T
  : never;

虽然也不算难，但是一看评论区天塌了。

type Integer<T extends string | number> = number extends T
  ? never
  : `${T}` extends `${string}.${string}`
  ? never
  : T;
// 或者这样，因为 bigint 只能是整数
type Integer<T extends number> = `${T}` extends `${bigint}` ? T : never

我自己试了一下数字转字符串，发现对于多余的小数点后面的 0 会被删除。

type x = `${1.0}` // "1"
type x1 = `${1.2}` // "1.2"
type x2 = `${1.200}` // "1.2"

89. Medium - 16259 - ToPrimitive ※

把对象中类型为字面类型（标签类型）的属性，转换为基本类型。

这题可以枚举类型实现，不过就没啥意思了。看到一种神奇的解法，用到了 valueOf。

type ToPrimitive<T> = T extends (...args: any[]) => any
  ? Function
  : T extends object
    ? { [K in keyof T]: ToPrimitive<T[K]> }
    : T extends { valueOf: () => infer R }
      ? R
      : T;

JavaScript 中每个包装对象都有 valueOf() 方法：

• String.prototype.valueOf() 返回 string
• Number.prototype.valueOf() 返回 number
• ...

在 TypeScript 类型系统中，我们可以利用这个特性：

interface String {
  /** Returns the primitive value of the specified object. */
  valueOf(): string;
  // ... 其他方法
}

// string 字面量类型
type Test1 = 'Tom' extends { valueOf: () => infer R } ? R : never
// 'Tom' 是 string 类型，string 有 valueOf(): string
// R = string ✅

type Test2 = 30 extends { valueOf: () => infer R } ? R : never
// 30 是 number 类型，number 有 valueOf(): number
// R = number ✅

90. Medium - 17973 - DeepMutable

实现一个通用的 DeepMutable ，它使对象的每个属性，及其递归的子属性 - 可变。

type DeepMutable<T extends object> = {
  -readonly [K in keyof T]: T[K] extends (...args: any) => any 
    ? T[K]
    : T[K] extends object ? DeepMutable<T[K]> : T[K]
}

1. 引言

HTTP 协议本质上是无状态（Stateless）的。在早期的单体应用时代，为了识别用户身份，我们通常依赖 Session-Cookie 机制：服务端在内存或数据库中存储 Session 数据，客户端浏览器通过 Cookie 携带 Session ID。

然而，随着微服务架构和分布式系统的兴起，这种有状态（Stateful）的机制暴露出了明显的弊端：Session 数据需要在集群节点间同步（Session Sticky 或 Session Replication），这极大地限制了系统的水平扩展能力（Horizontal Scaling）。

为了解决这一痛点，JSON Web Token（JWT）应运而生。作为一种轻量级、自包含的身份验证标准，JWT 已成为现代 Web 应用——特别是前后端分离架构与微服务架构中——主流的身份认证解决方案。本文将从原理剖析、NestJS 实战、架构权衡及高频面试考点四个维度，带你全面深入理解 JWT。

2. 什么是 JWT

JWT（JSON Web Token）是基于开放标准 RFC 7519 定义的一种紧凑且自包含的方式，用于在各方之间以 JSON 对象的形式安全地传输信息。

核心特性：

• 紧凑（Compact） ：体积小，可以通过 URL 参数、POST 参数或 HTTP Header 发送。
• 自包含（Self-contained） ：Payload 中包含了用户认证所需的所有信息，避免了多次查询数据库。

主要应用场景：

1. 身份认证（Authorization） ：这是最常见的使用场景。一旦用户登录，后续请求将包含 JWT，允许用户访问该令牌允许的路由、服务和资源。
2. 信息交换（Information Exchange） ：利用签名机制，确保发送者的身份是合法的，且传输的内容未被篡改。

3. JWT 的解剖学：原理详解

一个标准的 JWT 字符串由三部分组成，通过点（.）分隔：Header(请求头).Payload（载荷）.Signature（签名信息）。

3.1 Header（头部）

Header 通常包含两部分信息：令牌的类型（即 JWT）和所使用的签名算法（如 HMAC SHA256 或 RSA），一般会有多种算法，如果开发者无选择，那么默认是HMAC SHA256算法。

JSON

{
  "alg": "HS256",
  "typ": "JWT"
}

该 JSON 被 Base64Url 编码后，构成 JWT 的第一部分。

3.2 Payload（负载）

Payload 包含声明（Claims），即关于实体（通常是用户）和其他数据的声明。声明分为三类：

1. Registered Claims（注册声明） ：一组预定义的、建议使用的权利声明，如：

   • iss (Issuer): 签发者
   • exp (Expiration Time): 过期时间
   • sub (Subject): 主题（通常是用户ID）
   • aud (Audience): 受众

2. Public Claims（公共声明） ：可以由使用 JWT 的人随意定义。

3. Private Claims（私有声明） ：用于在同意使用这些定义的各方之间共享信息，如 userId、role 等。

架构师警示：
Payload 仅仅是进行了 Base64Url 编码（Encoding） ，而非 加密（Encryption） 。
这意味着，任何截获 Token 的人都可以通过 Base64 解码看到 Payload 中的明文内容。因此，严禁在 Payload 中存储密码、手机号等敏感信息。

3.3 Signature（签名）

签名是 JWT 安全性的核心。它是对前两部分（编码后的 Header 和 Payload）进行签名，以防止数据被篡改。

生成签名的公式如下（以 HMAC SHA256 为例）：

Code

HMACSHA256(
  base64UrlEncode(header) + "." + base64UrlEncode(payload),
  secret
)

原理解析：
服务端持有一个密钥（Secret），该密钥绝不能泄露给客户端。当服务端收到 Token 时，会使用同样的算法和密钥重新计算签名。如果计算出的签名与 Token 中的 Signature 一致，说明 Token 是由合法的服务端签发，且 Payload 中的内容未被篡改（完整性校验）。

4. 实战：基于 NestJS 实现 JWT 认证

NestJS 是 Node.js 生态中优秀的企业级框架。下面演示如何使用 @nestjs/jwt 和 @nestjs/passport 实现标准的 JWT 认证流程。

4.1 依赖安装

Bash

npm install --save @nestjs/passport passport @nestjs/jwt passport-jwt
npm install --save-dev @types/passport-jwt

4.2 Module 配置

在 AuthModule 中注册 JwtModule，配置密钥和过期时间。

TypeScript

// auth.module.ts
import { Module } from '@nestjs/common';
import { JwtModule } from '@nestjs/jwt';
import { PassportModule } from '@nestjs/passport';
import { AuthService } from './auth.service';
import { JwtStrategy } from './jwt.strategy';

@Module({
  imports: [
    PassportModule,
    JwtModule.register({
      secret: 'YOUR_SECRET_KEY', // 生产环境请使用环境变量
      signOptions: { expiresIn: '60m' }, // Token 有效期
    }),
  ],
  providers: [AuthService, JwtStrategy],
  exports: [AuthService],
})
export class AuthModule {}

4.3 Service 层：签发 Token

实现登录逻辑，验证用户信息通过后，生成 JWT。

TypeScript

// auth.service.ts
import { Injectable } from '@nestjs/common';
import { JwtService } from '@nestjs/jwt';

@Injectable()
export class AuthService {
  constructor(private readonly jwtService: JwtService) {}

  async login(user: any) {
    const payload = { username: user.username, sub: user.userId };
    return {
      access_token: this.jwtService.sign(payload),
    };
  }
}

4.4 Strategy 实现：解析 Token

编写策略类，用于解析请求头中的 Bearer Token 并进行验证。

TypeScript

// jwt.strategy.ts
import { ExtractJwt, Strategy } from 'passport-jwt';
import { PassportStrategy } from '@nestjs/passport';
import { Injectable } from '@nestjs/common';

@Injectable()
export class JwtStrategy extends PassportStrategy(Strategy) {
  constructor() {
    super({
      jwtFromRequest: ExtractJwt.fromAuthHeaderAsBearerToken(),
      ignoreExpiration: false, // 拒绝过期 Token
      secretOrKey: 'YOUR_SECRET_KEY', // 需与 Module 中配置一致
    });
  }

  async validate(payload: any) {
    // passport 会自动把返回值注入到 request.user 中
    return { userId: payload.sub, username: payload.username };
  }
}

4.5 Controller 使用：路由保护

TypeScript

// app.controller.ts
import { Controller, Get, UseGuards, Request } from '@nestjs/common';
import { AuthGuard } from '@nestjs/passport';

@Controller('profile')
export class ProfileController {
  @UseGuards(AuthGuard('jwt'))
  @Get()
  getProfile(@Request() req) {
    return req.user; // 这里是通过 JwtStrategy.validate 返回的数据
  }
}

5. 深度分析：JWT 的优缺点与架构权衡

优点

1. 无状态与水平扩展（Stateless & Scalability） ：服务端不需要存储 Session 信息，完全消除了 Session 同步问题，非常适合微服务和分布式架构。
2. 跨域友好：不依赖 Cookie（尽管可以结合 Cookie 使用），在 CORS 场景下处理更为简单，且天然适配移动端（iOS/Android）开发。
3. 性能：在不涉及黑名单机制的前提下，验证 Token 只需要 CPU 计算签名，无需查询数据库，减少了 I/O 开销。

缺点与挑战

1. 令牌体积：JWT 包含了 Payload 信息，相比仅存储 ID 的 Cookie，其体积更大，这会增加每次 HTTP 请求的 Header 大小，影响流量。
2. 撤销难题（Revocation） ：这是 JWT 最大 的痛点。JWT 一旦签发，在有效期内始终有效。服务端无法像 Session 那样直接删除服务器端数据来强制用户下线。

6. 面试高频考点与解决方案（进阶）

在面试中，仅仅展示如何生成 JWT 是远远不够的，面试官更关注安全性与工程化挑战。

问题 1：JWT 安全吗？如何防范攻击？

• XSS（跨站脚本攻击） ：如果将 JWT 存储在 localStorage 或 sessionStorage，恶意 JS 脚本可以轻松读取 Token。

  • 解决方案：建议将 Token 存储在标记为 HttpOnly 的 Cookie 中，这样 JS 无法读取。

• CSRF（跨站请求伪造） ：如果使用 Cookie 存储 Token，则会面临 CSRF 风险。

  • 解决方案：使用 SameSite=Strict 属性，或配合 CSRF Token 防御。如果坚持存储在 localStorage 并通过 Authorization Header 发送，则天然免疫 CSRF，但需重点防范 XSS。

• 中间人攻击：由于 Header 和 Payload 是明文编码。

  • 解决方案：必须强制全站使用 HTTPS。

问题 2：如何实现注销（Logout）或强制下线？

既然 JWT 是无状态的，如何实现“踢人下线”？这实际上是无状态与管控性之间的权衡。

• 方案 A：黑名单机制（Blacklist）

  • 将用户注销或被封禁的 Token ID (jti) 存入 Redis，设置过期时间等于 Token 的剩余有效期。
  • 每次请求验证时，先校验签名，再查询 Redis 是否在黑名单中。
  • 权衡：牺牲了部分“无状态”优势（引入了 Redis 查询），但获得了即时的安全管控。

• 方案 B：版本号/时间戳控制

  • 在 JWT Payload 中加入 token_version。
  • 在数据库用户表中也存储一个 token_version。
  • 当用户修改密码或注销时，增加数据库中的版本号。
  • 权衡：每次验证都需要查询数据库比对版本号，退化回了 Session 的模式，性能开销大。

问题 3：Token 续签（Refresh Token）机制是如何设计的？

为了解决 JWT 有效期过长不安全、过短体验差的问题，业界标准做法是 双 Token 机制：

1. Access Token：有效期短（如 15 分钟），用于访问业务接口。
2. Refresh Token：有效期长（如 7 天），仅用于换取新的 Access Token。

流程设计：

• 客户端请求接口，若 Access Token 过期，服务端返回 401。
• 客户端捕获 401，携带 Refresh Token 请求 /refresh 接口。
• 服务端验证 Refresh Token 合法（且未在黑名单/数据库中被禁用），签发新的 Access Token。
• 关键点：Refresh Token 通常需要在服务端（数据库）持久化存储，以便管理员可以随时禁用某个 Refresh Token，从而间接实现“撤销”用户的登录状态。

7. 结语

JWT 并不是银弹。它通过牺牲一定的“可控性”换取了“无状态”和“扩展性”。

在架构选型时：

• 如果你的应用是小型单体，且对即时注销要求极高，传统的 Session 模式可能更简单有效。
• 如果你的应用是微服务架构，或者需要支持多端登录，JWT 是不二之选。
• 在构建企业级应用时，切勿盲目追求纯粹的无状态。推荐使用 JWT + Access/Refresh Token 双令牌 + Redis 黑名单 的组合拳，以在安全性、性能和扩展性之间取得最佳平衡。

LeetCode简单难度的经典二叉树题目——100. 相同的树，这道题虽然难度不高，但非常适合入门二叉树的遍历思想，尤其是递归和迭代两种核心思路的对比练习，新手朋友可以重点看看，老手也可以快速回顾巩固一下。

先简单梳理一下题目要求，避免踩坑：给两棵二叉树的根节点p和q，判断这两棵树是否“相同”。这里的相同有两个核心条件，缺一不可：结构上完全一致，并且对应位置的节点值完全相等。

举个直观的例子：如果p是一棵只有根节点（值为1）的树，q也是只有根节点（值为1），那它们是相同的；但如果p的根节点是1、左孩子是2，q的根节点是1、右孩子是2，哪怕节点值都一样，结构不同，也不算相同。

一、题目前置准备

题目已经给出了二叉树节点的定义，用TypeScript实现的，这里再贴一遍，方便大家对照代码理解（注释已补充，新手可重点看构造函数的逻辑）：

class TreeNode {
  val: number; // 节点值
  left: TreeNode | null; // 左孩子，可能为null（没有左孩子）
  right: TreeNode | null; // 右孩子，可能为null（没有右孩子）
  // 构造函数：初始化节点，val默认0，左右孩子默认null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val); // 节点值为空时，默认设为0
    this.left = (left === undefined ? null : left); // 左孩子为空时，默认设为null
    this.right = (right === undefined ? null : right); // 右孩子为空时，默认设为null
  }
}

二、解法一：递归解法

1. 递归思路分析

递归的核心思想是“分而治之”，把判断两棵大树是否相同，拆解成判断无数个“小问题”——判断当前两个节点是否相同，以及它们的左孩子、右孩子是否分别相同。

递归的终止条件（也是边界情况）很关键，分三步判断，逻辑层层递进：

• 如果p和q都为null（两个节点都不存在）：说明这两个位置的节点是相同的，返回true；

• 如果p和q中一个为null、另一个不为null（一个节点存在，一个不存在）：说明结构不同，返回false；

• 如果p和q都不为null，但它们的val不相等（节点值不同）：说明节点不相同，返回false；

如果以上三种情况都不满足，说明当前两个节点是相同的，接下来就递归判断它们的左孩子（p.left和q.left）和右孩子（p.right和q.right），只有左右孩子都相同，整棵树才相同（用&&连接两个递归结果）。

2. 递归代码实现

// 递归解法：isSameTree_1
function isSameTree_1(p: TreeNode | null, q: TreeNode | null): boolean {
  // 边界情况1：两个节点都为空，相同
  if (p === null && q === null) {
    return true;
  }
  // 边界情况2：一个为空，一个不为空，结构不同，不相同
  if (p === null || q === null) {
    return false;
  }
  // 边界情况3：两个节点都不为空，但值不同，不相同
  if (p.val !== q.val) {
    return false;
  }
  // 递归：当前节点相同，判断左孩子和右孩子是否都相同
  return isSameTree_1(p.left, q.left) && isSameTree_1(p.right, q.right);
};

3. 递归解法总结

优点：代码极度简洁，逻辑清晰，完全贴合二叉树的递归特性，容易理解和编写，新手友好；

缺点：递归依赖调用栈，如果二叉树深度极深（比如链式二叉树），可能会出现栈溢出的情况（但LeetCode的测试用例一般不会卡这种极端情况，日常刷题完全够用）；

时间复杂度：O(n)，n是两棵树中节点数较少的那一个，每个节点只会被访问一次；

空间复杂度：O(h)，h是树的高度，最坏情况下（链式树）h=n，最好情况下（平衡树）h=logn。

三、解法二：迭代解法（用栈模拟递归，避免栈溢出）

1. 迭代思路分析

迭代解法的核心是“用栈模拟递归的调用过程”，通过手动维护一个栈，把需要判断的节点对（p的节点和q的对应节点）压入栈中，然后循环弹出节点对进行判断，本质上和递归的逻辑是一致的，只是实现方式不同。

具体步骤：

1. 先判断两棵树的根节点是否都为空（和递归边界1一致），如果是，直接返回true；

2. 如果根节点一个为空、一个不为空（和递归边界2一致），直接返回false；

3. 初始化一个栈，把根节点对（p和q）压入栈中（注意压入顺序，后续弹出时要对应）；

4. 循环：只要栈不为空，就弹出两个节点（pNode和qNode），进行判断；

5. 判断弹出的两个节点：如果都为空，跳过（继续判断下一组节点）；如果一个为空一个不为空，返回false；如果值不相等，返回false；

6. 如果当前节点对相同，就把它们的左孩子对、右孩子对依次压入栈中（注意压入顺序，先压右孩子，再压左孩子，因为栈是“后进先出”，和递归的顺序保持一致）；

7. 循环结束后，说明所有节点对都判断完毕，没有发现不相同的情况，返回true。

这里有个小细节：压入栈的顺序是“p.left、q.left、p.right、q.right”，弹出的时候会先弹出p.right和q.right，再弹出p.left和q.left，和递归时“先判断左孩子，再判断右孩子”的顺序是一致的，不影响结果，但要注意保持对应关系，不能压混。

2. 迭代代码实现

// 迭代解法：isSameTree_2（栈模拟递归）
function isSameTree_2(p: TreeNode | null, q: TreeNode | null): boolean {
  // 先处理根节点的边界情况（和递归一致）
  if (p === null && q === null) {
    return true;
  }
  if (p === null || q === null) {
    return false;
  }
  // 初始化栈，压入根节点对（p和q）
  let stack: (TreeNode | null)[] = [];
  stack.push(p);
  stack.push(q);
  
  // 循环：栈不为空时，持续判断节点对
  while (stack.length > 0) {
    // 弹出两个节点，注意栈是后进先出，所以先弹出q，再弹出p（对应压入顺序）
    let qNode: TreeNode | null = stack.pop() ?? null;
    let pNode: TreeNode | null = stack.pop() ?? null;
    
    // 两个节点都为空，跳过（继续判断下一组）
    if (pNode === null && qNode === null) {
      continue;
    }
    // 一个为空一个不为空，结构不同，返回false
    if (pNode === null || qNode === null) {
      return false;
    }
    // 节点值不同，返回false
    if (pNode.val !== qNode.val) {
      return false;
    }
    
    // 当前节点对相同，压入它们的左孩子对和右孩子对（保持对应关系）
    stack.push(pNode.left);
    stack.push(qNode.left);
    stack.push(pNode.right);
    stack.push(qNode.right);
  }
  
  // 所有节点对都判断完毕，没有不相同的情况，返回true
  return true;
}

3. 迭代解法总结

优点：不依赖递归调用栈，避免了极端情况下的栈溢出问题，稳定性更好；

缺点：代码比递归稍长，需要手动维护栈和循环逻辑，对新手来说稍微复杂一点；

时间复杂度：O(n)，和递归一致，每个节点只会被压入栈、弹出栈各一次，访问一次；

空间复杂度：O(n)，最坏情况下（平衡树），栈中会存储n/2个节点对，空间复杂度为O(n)；最好情况下（链式树），栈中最多存储2个节点对，空间复杂度为O(1)。

四、两种解法对比 & 刷题建议

解法类型	优点	缺点	适用场景
递归	代码简洁、逻辑清晰、易编写	极端情况下可能栈溢出	日常刷题、二叉树深度不深的场景
迭代（栈）	无栈溢出问题、稳定性好	代码稍长、需维护栈逻辑	二叉树深度极深、生产环境场景

刷题建议：新手先掌握递归解法，因为它最贴合二叉树的特性，后续做二叉树的遍历、对称树、翻转树等题目时，思路可以无缝迁移；掌握递归后，再理解迭代解法，重点体会“栈模拟递归”的思想，这是二叉树迭代题目的核心套路。

五、常见踩坑点提醒

• 踩坑点1：忽略“结构不同”的情况，只判断节点值。比如p有左孩子、q没有左孩子，但其他节点值都相同，此时会误判为相同；

• 踩坑点2：递归时忘记写终止条件，导致无限递归，栈溢出；

• 踩坑点3：迭代时压入栈的节点对顺序混乱，导致弹出时判断的不是“对应节点”（比如把p.left和q.right压在一起）；

• 踩坑点4：处理节点为null时不严谨，比如用p.val === q.val时，没有先判断p和q是否为null，导致空指针错误（代码中已规避此问题）。

六、总结

LeetCode 100. 相同的树，本质上是二叉树“同步遍历”的入门练习，核心是判断“结构+节点值”是否双匹配。递归解法胜在简洁，迭代解法胜在稳定，两种解法的逻辑完全一致，只是实现方式不同。

刷这道题的重点不在于“写出代码”，而在于理解“如何同步判断两棵树的对应节点”，这个思路后续会用到很多类似题目中（比如101. 对称二叉树，只是判断的是“自身的左孩子和右孩子”，逻辑高度相似）。

LeetCode基础题第104题「二叉树的最大深度」，这道题是二叉树遍历的经典入门题，核心考察对二叉树层次遍历（BFS）的理解和应用，适合新手入门练手。今天就来详细拆解这道题，从题目理解到代码实现，再到细节优化，一步步讲清楚，看完就能轻松掌握。

一、题目解读

题目描述

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

简单来说，就是要找到二叉树“最深”的那一层，统计从根到这一层的所有节点个数。举个例子：

• 如果二叉树只有根节点，没有左右子节点，最大深度就是1；

• 如果根节点有左子节点，左子节点又有一个子节点，那么最大深度就是3；

• 如果二叉树是空树（root为null），最大深度就是0。

核心考点

这道题的核心是「二叉树的遍历」，常见的解法有两种：

1. 层次遍历（BFS，广度优先搜索）：按层遍历二叉树，每遍历完一层，深度加1，最终的深度就是最大深度（本文重点讲解这种解法，对应给出的代码）；

2. 深度优先搜索（DFS）：递归遍历左右子树，取左右子树的最大深度，再加上当前根节点的深度1，即为整个树的最大深度（后续会补充备选代码）。

二、代码解析（TypeScript）

先贴出完整代码（已优化，解决原代码潜在问题），再逐行拆解思路，新手也能看懂～

/**
 * Definition for a binary tree node.
 * 二叉树节点的定义（题目已给出，无需修改）
 */
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 === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

/**
 * 计算二叉树最大深度（层次遍历/BFS解法）
 * @param root 二叉树根节点
 * @returns 二叉树的最大深度
 */
function maxDepth(root: TreeNode | null): number {
  // 边界处理：空树直接返回深度0（避免后续无效循环）
  if (root === null) {
    return 0;
  }

  let depth = 0; // 记录当前深度，初始化为0
  // 用数组模拟队列，存储当前层的所有节点（初始存入根节点）
  const queue: TreeNode[] = [root];

  // 队列不为空，说明还有节点未遍历，继续循环
  while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点个数
    // 遍历当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      // 取出当前层的节点（优化：用pop+unshift替代shift，提升性能）
      const node = queue.pop()!;
      
      // 若当前节点有右子节点，存入队列（先存右，再存左，保证遍历顺序）
      if (node.right) {
        queue.unshift(node.right);
      }
      // 若当前节点有左子节点，存入队列
      if (node.left) {
        queue.unshift(node.left);
      }
    }
    // 可选：打印队列，观察每一层遍历后的节点变化（调试用）
    
    
    // 当前层遍历完毕，深度加1
    depth++;
  }

  return depth;
}

逐行拆解思路

1. 边界处理（关键！）

if (root === null) { return 0; }

这一步是很多新手容易忽略的点：如果二叉树是空树（root为null），没有任何节点，最大深度自然是0。如果不做这个判断，后续队列会存入null，导致循环多执行一次，最终返回错误的深度1。

2. 初始化变量

• let depth = 0;：用于记录二叉树的深度，初始值为0（因为还未开始遍历任何一层）；

• const queue: TreeNode[] = [root];：用数组模拟队列（队列是BFS的核心数据结构），初始时将根节点存入队列，代表从根节点开始遍历。

3. 层次遍历核心循环

while (queue.length > 0) { ... }：队列不为空，说明还有节点未遍历，循环继续。每一次循环，都代表遍历完「一层」节点。

4. 遍历当前层节点

const levelSize = queue.length;：获取当前层的节点个数，这个值是固定的（因为后续队列会存入下一层的节点，不能直接用queue.length判断当前层节点数）。

for (let i = 0; i < levelSize; i++) { ... }：循环遍历当前层的每一个节点，把每个节点的左右子节点（如果有的话）存入队列，为下一层遍历做准备。

5. 节点取出与子节点入队（性能优化点）

原代码中如果用queue.shift()取出节点，会有性能问题——因为数组的shift()方法是O(n)时间复杂度（需要将数组中所有元素向前移动一位），当二叉树节点较多时，效率会很低。

优化方案：用queue.pop()（O(1)时间复杂度）取出队列尾部的节点，同时调整子节点入队顺序（先存右子节点，再存左子节点），保证遍历顺序和shift()一致，既提升性能，又不影响结果。

这里的!是非空断言，因为我们已经通过边界处理和循环条件，确保队列中的节点一定是TreeNode类型（不会为null），所以可以安全使用非空断言。

6. 深度递增

depth++;：每遍历完一层，说明二叉树的深度增加了1，所以深度加1。当循环结束时，depth就是二叉树的最大深度。

三、代码优化说明

对比LeetCode题目给出的初始模板，这段代码做了3个关键优化，兼顾性能和正确性：

1. 新增边界处理：解决空树返回错误深度的问题，让代码更健壮；

2. 性能优化：用pop() + unshift()替代shift()，将节点取出操作的时间复杂度从O(n)降至O(1)，适合处理节点较多的二叉树；

可读性优化：添加详细注释，变量命名语义化（如levelSize代表当前层节点数），方便新手理解每一步的执行过程。

四、备选解法（DFS递归版）

除了上述层次遍历（BFS）解法，这道题还可以用深度优先搜索（DFS）的递归写法，代码更简洁，适合树深度不大的场景（避免递归栈溢出），新手也可以了解一下：

function maxDepthRecursive(root: TreeNode | null): number {
  // 空树返回0
  if (root === null) {
    return 0;
  }
  // 递归计算左右子树的最大深度，当前深度 = 左右子树最大深度 + 1（当前节点）
  return Math.max(maxDepthRecursive(root.left), maxDepthRecursive(root.right)) + 1;
}

递归解法的核心思路：二叉树的最大深度 = 左子树最大深度和右子树最大深度的最大值 + 1（当前根节点），本质是遍历到最底层的叶子节点，再回溯计算深度。

五、总结

LeetCode 104题是二叉树遍历的入门题，难度简单，但能很好地巩固BFS和DFS的基础思路。本文讲解的层次遍历（BFS）解法，适合所有场景（包括极深的二叉树，避免递归栈溢出），优化后的代码兼顾性能和可读性，新手可以重点掌握。

解题关键记住两点：

1. 边界处理：空树直接返回0，避免错误；

2. 层次遍历核心：用队列存储每一层的节点，每遍历完一层，深度加1。

同步至个人站点：Memo Code 安全设计：子进程、命令防护与权限审批的统一方案

Memo Code 是我最近两个多月投入较多精力的 Agent 项目。类似于Claude Code 和 Codex 的 轻量级本地编程 Agent，目前已具备 Coding Agent 完备技能。

如果你感兴趣的话，欢迎参与：Memo Code - Github，或者给个 Star 鼓励一下哈哈～

做 Agent 这类能「替用户干活」的工具，安全性是躲不掉的坎。

我一开始做 memo（github.com/minorcell/m…）的时候，安全问题还没想那么多——能跑起来就行。后来工具越加越多，shell 命令也越跑越复杂，就开始踩坑了：

• 子进程忘了关，内存慢慢涨
• rm -rf / 差点真被我跑出来
• 每次执行都要点批准，用户体验稀碎

这些问题逼着我认真设计了整套安全方案。今天把思路和实现细节都分享出来，希望对你有帮助。

先想清楚：安全设计要解决什么问题？

我把它拆成三件事：

1. 资源可控：子进程不能无限开，不能忘了关
2. 操作安全：危险命令要拦截，误操作要有缓冲
3. 权限平衡：该拦的拦住，该放的放行，还要给用户留个「后门」

下面逐一展开。

第一道防线：子进程管理——防止内存泄漏与资源耗尽

memo 的 shell 执行用的是 Node.js 的 child_process.spawn，但光 spawn 是不够的——你还得管得住。

统一会话管理器

我写了一个 UnifiedExecManager（packages/tools/src/tools/exec_runtime.ts），核心思路是单例 + 会话池：

class UnifiedExecManager {
  private sessions = new Map<number, SessionState>()
  private nextId = 1
  private MAX_SESSIONS = 64
}

好处很明显：

• 所有子进程都有唯一 ID
• 随时可以查询状态、发送信号、获取输出
• 资源回收有统一入口

资源限制：数量 + 内存 + 时间

先看数量限制：

async start(request: StartExecRequest) {
    this.cleanupSessions()
    if (this.activeSessionCount() >= MAX_SESSIONS) {
        throw new Error(`too many active sessions (max ${MAX_SESSIONS})`)
    }
    // ...
}

超过 64 个活跃会话就直接拒绝，防止被LLM恶意耗尽系统资源。

再看输出限制。Agent 交互是基于 token 计费的，子进程输出不能无限制返回：

function truncateByTokens(text: string, maxOutputTokens?: number) {
  const maxChars = (maxOutputTokens || 2000) * 4
  if (text.length <= maxChars) {
    return { output: text, deliveredChars: text.length }
  }
  return {
    output: text.slice(0, maxChars),
    deliveredChars: maxChars,
  }
}

默认最多返回 8000 字符，不够可以调，但不会无限大。

超时终止：SIGTERM → SIGKILL

子进程跑飞了是常见问题。memo 的策略是先礼貌后强硬：

private async terminateForTimeout(session: SessionState) {
    if (session.exited) return
    session.proc.kill('SIGTERM')
    await waitForExit(session, 200)  // 等 200ms
    if (!session.exited) {
        session.proc.kill('SIGKILL')  // 还是没退就直接杀了
        await waitForExit(session, 200)
    }
}

为什么要等一下？因为有些程序接收到 SIGTERM 会做清理工作（比如写入缓存、关闭句柄），直接 SIGKILL 可能导致数据丢失。

内存泄漏防护：自动清理已退出的会话

会话不能只增不减。我加了一个自动清理逻辑：

private cleanupSessions() {
    if (this.sessions.size <= MAX_SESSIONS) return
    // 优先清理已退出的，按启动时间从早到晚排序
    const ended = Array.from(this.sessions.values())
        .filter(session => session.exited)
        .sort((a, b) => a.startedAtMs - b.startedAtMs)

    for (const session of ended) {
        if (this.sessions.size <= MAX_SESSIONS) break
        this.sessions.delete(session.id)
    }
}

这样即使跑了几百个命令，内存也不会无限涨。

第二道防线：命令守卫——拦截危险操作

子进程管住了还不够，还得管住跑什么命令。

我见过太多「rm -rf /」惨案，也见过 dd if=/dev/zero of=/dev/sda 这种物理层面不可逆的破坏。memo 的做法是命令解析 + 黑名单匹配。

命令解析：不只是字符串匹配

直接正则匹配 rm -rf 是有漏洞的。比如 sudo rm -rf /、包裹在 bash -c 里、甚至写成十六进制，都能绕过简单匹配。

memo 的做法是先把命令拆成「段」，再逐段解析：

function splitCommandSegments(command: string) {
  // 按 ; | && || 分割，处理引号和转义
  // 返回每一段独立的命令
}

function parseSegment(segment: string) {
  // 跳过 sudo/env/nohup 等包装
  // 提取真实的命令名和参数
}

这样不管外面包了多少层 sudo env bash -c，最终都能追溯到真正的命令。

危险命令黑名单

目前 memo 拦截这几类（packages/tools/src/tools/command_guard.ts）：

规则	触发条件	危险等级
rm_recursive_critical_target	rm -rf 目标包含 /、~、$HOME 等关键路径	极高
mkfs_filesystem_create	mkfs/mkfs.xxx	极高
dd_write_block_device	dd 写入 /dev/ 下的块设备	极高
disk_mutation_block_device	fdisk/parted/shred 等操作块设备	高
redirect_block_device	输出重定向到 /dev/ 块设备	高

拦截后返回的是 <system_hint> 标记，不是直接报错，方便 Agent 理解为什么被拦：

<system_hint type="tool_call_denied"
    tool="exec_command"
    reason="dangerous_command"
    policy="blacklist"
    rule="rm_recursive_critical_target"
    command="rm -rf /">
    Blocked a high-risk shell command to prevent irreversible data loss.
    Use a safer and scoped alternative.
</system_hint>

第三道防线：审批系统——平衡权限与体验

命令守卫是第一道关卡，但还有很多「不危险但需要知道」的操作，比如写文件、改配置。审批系统的目标就是分级管理、可追溯、可配置。

风险分级

memo 把工具分成三级（packages/tools/src/approval/constants.ts）：

级别	含义	审批策略（auto 模式）
read	只读操作	免审批
write	文件修改	需审批
execute	执行命令	需审批

审批模式

• auto 模式：只读工具免审批，写/执行类工具需要审批
• strict 模式：所有工具都需要审批，一个都跑不掉

check(toolName: string, params: unknown): ApprovalCheckResult {
    if (ALWAYS_AUTO_APPROVE_TOOLS.has(toolName)) {
        return { needApproval: false, decision: 'auto-execute' }
    }

    const riskLevel = classifier.getRiskLevel(toolName)
    if (!classifier.needsApproval(riskLevel, approvalMode)) {
        return { needApproval: false, decision: 'auto-execute' }
    }
    // 生成指纹，返回需要审批
}

审批记忆：一次批准，记住一整场

如果每次执行都要点批准，用户体验会非常差。memo 用指纹 + 缓存解决这个问题：

const fingerprint = generateFingerprint(toolName, params)
cache.toolByFingerprint.set(fingerprint, toolName)

// 审批后记录
recordDecision(fingerprint, decision: 'session' | 'once' | 'deny') {
    switch (decision) {
        case 'session': cache.sessionTools.add(toolName); break
        case 'once': cache.onceTools.add(toolName); break
        case 'deny': cache.deniedTools.add(toolName); break
    }
}

• session：这场对话内一直有效
• once：用一次就失效
• deny：以后再问直接拦截

dangerous 模式

审批系统是安全了，但有时候用户就是想要「无限制」——比如在本地开发、或者明确知道自己在干什么。

memo 提供了 dangerous 模式：

if (dangerous) {
  return {
    isDangerousMode: true,
    getRiskLevel: () => 'read', // 所有操作都视为最低风险
    check: () => ({ needApproval: false, decision: 'auto-execute' }),
    isGranted: () => true,
  }
}

开启也很简单，CLI 里加上 --dangerous 标记：

memo --dangerous

开启后：

• 所有工具都免审批

这是一把双刃剑。 我在 CLI 里加了这个选项，但默认是关闭的。开发者如果想用，需要明确加上 --dangerous 标记。

总结：三层防护 + 一个后门

memo 的安全设计可以总结为：

1. 子进程管理：数量限制 + 输出截断 + 超时终止 + 自动清理
2. 命令守卫：命令解析 + 黑名单拦截 + stdin 检测
3. 审批系统：风险分级 + 审批模式 + 记忆缓存
4. dangerous 模式：留一个「我知道我在干什么」的后门

这套方案不完美，还在持续迭代。比如命令守卫目前是硬编码的黑名单，后续可以考虑支持用户自定义规则；审批系统也可以考虑接入外部信任模型。

（完）