快速上手——从0到1掌握算法面试需要的数据结构（三）|算法篇
# 理解树结构
30 秒速记
- 树是无环的连通层级结构；除根结点外，每个结点恰好有一个父结点，可以有零个或多个子结点
- 结点的度是直接子结点数量，叶子结点的度为
0；树的度是所有结点度的最大值 - 深度从根向下数，高度从叶向上数；面试前必须先约定根深度和叶高度从
0还是1开始 - 含
n个结点的树恰有n - 1条边；多一条边会成环，少一条边会不连通 - 递归处理树时先定义“函数返回的子树信息”，再组合左右或所有孩子，避免只背遍历模板
树本质上是无环且连通的层级结构，除根结点外，每个结点只有一个父结点，但可以有多个子结点。 结点的度表示直接子结点数量，度为 0 的是叶子结点，而树的度取所有结点度的最大值。深度从根向下计算，高度从叶子向上计算，不同教材可能从 0 或 1 起算，所以面试时要先讲清口径。含 n 个结点的树有 n - 1 条边；递归处理时应先定义函数返回什么子树信息，并注意退化成链后递归栈可能达到 O(n)。
树的术语容易因为教材口径不同而答乱。下面统一约定根结点深度为 0、叶结点高度为 0：结点深度等于从根到它的边数，结点高度等于从它到最远叶子的边数。若题目把层数从 1 开始，只需整体加一，算法本身不变。面试时先说清口径，比死背某个数字更可靠。
function measureTree(root) {
let maxDepth = -1
let nodeCount = 0
function height(node, depth) {
if (node === null) return -1
nodeCount += 1
maxDepth = Math.max(maxDepth, depth)
const childHeights = (node.children ?? []).map((child) => height(child, depth + 1))
return 1 + Math.max(-1, ...childHeights)
}
const treeHeight = height(root, 0)
return { nodeCount, maxDepth, treeHeight }
}
空树返回高度 -1，因此叶结点会得到 1 + (-1) = 0。每个结点只访问一次，时间复杂度 O(n)；递归栈等于树高 O(h)，退化成链时可能达到 O(n) 并触发调用栈上限，超深输入应改用显式栈。
在理解计算机世界的树结构之前，大家不妨回忆一下现实世界中的树有什么特点：一棵树往往只有一个树根，向上生长后，却可以伸展出无数的树枝、树枝上会长出树叶。由树根从泥土中吸收水、无机盐等营养物质，源源不断地输送到树枝与树叶的那一端。一棵树往往呈现这样的基本形态：
数据结构中的树，首先是对现实世界中树的一层简化：把树根抽象为“根结点”，树枝抽象为“边”，树枝的两个端点抽象为“结点”，树叶抽象为“叶子结点”。抽象后的树结构如下：
把这棵抽象后的树颠倒一下，就得到了计算机中的树结构：
结合这张图，我们来讲解树的关键特性和重点概念。希望大家可以牢记以下几点：
- 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
- 结点和树的“高度”计算规则：叶子结点高度记为1，每向上一层高度就加1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。
- “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。比如我们上图中，根结点的“度”就是3。
- “叶子结点”：叶子结点就是度为0的结点。在上图中，最后一层的结点的度全部为0，所以这一层的结点都是叶子结点。
面试官追问
追问 1组织架构页把根部门标成“第 1 层”，算法库却返回根结点深度 0；前后端都声称自己正确，你如何消除这个口径冲突？
两种口径都可能自洽，冲突来自把层数与按边计数的深度混用。接口应明确根为 depth=0，若展示层数则使用 level=depth+1，并分别测试根、直接子结点和空树；字段名含糊时不能依靠调用方猜测。
追问 2权限树接口返回 10 个结点和 10 条父子边，数据团队说“每个结点都找得到父级，所以是树”，你会怎样反驳并校验？
非空树若有 n 个结点只能有 n-1 条边，额外边意味着至少有环或不符合单父结点约束。校验时还要确认只有一个根、每个非根结点恰有一个父结点且整体连通；仅能查到父级无法排除循环引用。
追问 3评论页面需要计算整棵树的结点数、最大深度和树高，你会一次遍历还是分别写三个递归函数？
一次深度优先遍历就能累计结点数、更新最大深度，并在回溯时计算每个结点的高度，时间为 O(n)。约定空树高度为 -1、叶结点高度为 0 后公式更统一；合并遍历会增加函数职责，需用清晰返回值保持可验证性。
追问 4线上评论数据退化成十万层单链，统计函数时间复杂度仍是 O(n) 却触发 Maximum call stack size exceeded，你怎么修？
故障来自递归栈深度等于树高，退化链会把空间从通常的层级深度推到 O(n)。应改用显式栈迭代，并在数据入口限制异常层级或检测非法结构；迭代避免调用栈上限，但显式容器仍需要与树高相关的空间。
追问 5文件目录页只要逐层渲染可见结点，组件作者选深度优先，交互负责人坚持广度优先；你会依据什么取舍？
若界面按层加载和展示，广度优先更直接，也便于得到层级信息，但宽层会让队列占用较多内存。深度优先适合沿分支处理，显式栈通常与树高相关；选择应服从渲染顺序、树宽树高和是否需要提前停止，而不是只比较 O(n) 时间。
# 理解二叉树结构
30 秒速记
- 二叉树允许为空；每个结点最多有左、右两个孩子，并且左右位置有语义，不能随意交换
- “最多两个孩子”不等于“每个结点度都为
2”；只有所有内部结点恰有两个孩子时才是满二叉树 - 完全二叉树只允许最后一层不满且必须从左到右连续，适合用数组按下标存储堆
- 二叉搜索树额外约束键值顺序，平衡树额外限制高度；它们都是二叉树的特例，不能反向推出
- 题目序列化必须携带空位置，否则仅凭先序或层序值通常不能唯一还原树形
二叉树可以为空；非空时，每个结点最多有左、右两个孩子，而且左右位置属于结构的一部分，不能随意互换。 “最多两个孩子”不代表每个结点的度都是 2，只有内部结点都恰好有两个孩子时，才满足满二叉树的要求。完全二叉树只允许最后一层不满，并且结点必须从左到右连续，因此适合按下标存进数组。序列化时还要保留 null 等空位标记，否则仅凭 [1, 2] 这样的先序或层序值，通常无法判断 2 是左孩子还是右孩子。
二叉树的左右位置是结构的一部分。一个只有左孩子的根，与只有右孩子的根即使值相同也是两棵不同的树。也正因为空位携带信息，序列化时不能简单过滤 null：先序值 [1, 2] 无法判断 2 在左边还是右边。
function serialize(root) {
const output = []
const visit = (node) => {
if (node === null) {
output.push('#')
return
}
output.push(String(node.val))
visit(node.left)
visit(node.right)
}
visit(root)
return output.join(',')
}
每个真实结点及其空孩子标记各处理一次，时间与输出空间都是 O(n)。若结点值可能包含逗号或 #，生产实现要使用长度前缀或 JSON 编码，不能依赖脆弱的字符串分隔符。
二叉树是指满足以下要求的树：
- 它可以没有根结点，作为一棵空树存在
- 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：
注意，二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。对应到图上来看，也就意味着 B 和 C、D 和 E、F 和 G 是不能互换的。
面试官追问
追问 1配置页有两棵结点值都为 [1,2] 的二叉树，一棵把 2 放左边，另一棵放右边；同事说值序列相同就应判等，你怎么说明反例？
二叉树的左右位置属于结构本身，这两棵树即使结点值完全相同也不相等。判等必须同时比较当前值、左子树和右子树；若业务只关心无序层级关系，那已经是另一种数据模型，不能继续沿用二叉树结构相等语义。
追问 2前端要把二叉树保存到 localStorage，开发者用先序遍历得到 [1,2] 并删除所有空位；恢复时为什么无法确定 2 的位置？
删除空位后，序列无法区分 2 是根的左孩子还是右孩子，反序列化缺少唯一结构信息。先序方案应为每个空孩子写入明确标记，并按相同顺序读取；若值域可能包含标记符或分隔符，还要使用 JSON 或长度前缀编码。
追问 3消息协议原先保证结点值全是数字，现在允许逗号和字符 #；现有序列化结果用逗号分隔并以 # 表示空结点，你会怎样调整？
现有格式会把合法值误解析成分隔符或空位标记，因此已不再可逆。应改用结构化 JSON、长度前缀或带转义规则的编码，并为旧数据保留明确的版本识别；仅替换一个特殊字符会把冲突推迟到未来值域扩展。
追问 4线上反序列化偶发生成左右孩子错位的树，但结点数量和数值都正确；你会优先核对哪些读写约定？
先核对序列化与反序列化是否采用相同遍历顺序，以及两端是否都消费了空孩子标记。再用只有左孩子、只有右孩子和单结点树做最小复现，观察游标每次消费的位置；只校验值和数量无法发现左右结构被交换。
追问 5堆模块评审时，有人说“结点最多两个孩子，所以普通二叉树都能直接用数组下标公式存储”，你会如何纠正选型？
数组下标映射更适合完全二叉树，因为结点位置连续，空洞较少；普通稀疏二叉树若强行按位置展开，可能产生大量无效槽位。对象引用能自然保留左右位置，但有额外引用开销；存储方式应结合树形约束与访问模式决定。
# 二叉树的编码实现
30 秒速记
- 结点模型至少包含值、左孩子、右孩子；空孩子统一用
null，避免undefined、缺字段和null混用 - 构造树要明确输入格式：嵌套对象、带空位的层序数组或边集合，三者的校验方式不同
- 遍历前先处理
root === null；递归简洁但受栈深限制，深树使用显式栈或队列 - 树可能来自不可信接口，必须防环和共享子结点，否则“遍历树”会死循环或重复处理同一对象
- 生产模型还应考虑不可变更新、父指针是否需要、重复键和序列化协议，不能只定义三个字段
二叉树结点至少要保存值、左孩子和右孩子，缺失的孩子统一用 null 表示。 构造时必须约定输入格式，例如带空位的层序数组中，null 表示孩子缺失，但数值 0 和空字符串仍是合法结点值，不能用真假判断过滤。遍历前要处理 root === null；递归写法更直观，但树退化得很深时可能触发调用栈上限，此时应换成显式栈或队列。若数据来自不可信接口，还要防止环和共享子结点，否则遍历可能死循环或重复处理同一对象。
