# 理解树结构
30 秒速记
- 树 = 连通、无环的层级结构；除根以外每个结点恰好一个父结点
- 度 = 直接子结点个数，度为
0的是叶子；树的度取所有结点度的最大值 - 深度从根往下数，高度从叶往上数；从
0还是1起算各教材不同，先说清口径 n个结点恰好n - 1条边：多一条成环，少一条不连通- 递归先想清楚「函数返回这棵子树的什么信息」；链状退化的树递归深度是
O(n)，可能爆栈
树就是一个没有环、所有结点连在一起的层级结构，除了根，每个结点只有一个父亲。 生活里最像的就是公司组织架构或者电脑里的文件夹，一个上级可以管很多人，但每个人只有一个直属上级。几个术语要分清：度是直接孩子的个数，叶子是没有孩子的结点；深度从根往下数，高度从最远的叶子往上数。不同教材从 0 或 1 起算，比如层数常从 1 开始，我面试时会先说一句「我按根深度为 0 来算」，避免双方对不上。
树的术语容易因为教材口径不同而答乱。下面统一约定根结点深度为 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，字段名别都叫 level 让人猜。
追问 2权限树接口返回 10 个结点和 10 条父子边，能是一棵树吗？
不能。n 个结点的树只能有 n - 1 条边，多出来的那条一定造成了环或者某个结点有两个父亲。
追问 3要同时算结点总数、最大深度和树高，你会写三个函数吗？
一次 DFS 就够：进入结点时计数、用当前深度更新最大深度，回溯时用孩子的高度算自己的高度。时间 O(n)，比遍历三遍省事。
追问 4评论数据退化成十万层的单链，递归统计报 Maximum call stack size exceeded，怎么修？
递归深度等于树高，十万层直接把调用栈撑爆了。改成自己维护数组当栈的迭代写法，入口也可以限制一下嵌套层数。
追问 5文件目录要按层展开渲染，用 DFS 还是 BFS？
BFS，它天然一层一层出来，用队列很好写。DFS 适合沿着一条分支走到底，比如找某个文件的完整路径。
# 理解二叉树结构
30 秒速记
- 二叉树可以是空树；非空时每个结点最多两个孩子，而且分左右，不能互换
- 「最多两个」不是「每个都有两个」，所有非叶结点都恰好两个孩子的才叫满二叉树（国内教材通常还要求所有叶子在同一层）
- 完全二叉树：只有最后一层可以不满，且从左往右连续 → 能用数组存，堆就是这么存的
- 二叉搜索树（左小右大）、平衡树（限制高度）都是二叉树的特例
- 序列化必须保留空位，只有
[1, 2]分不清2在左还是在右
二叉树就是每个结点最多有左右两个孩子的树，而且左和右是有区别的，不能随便交换。 这点和普通树不一样，普通树的孩子没有左右之分；二叉树里一个根只有左孩子，和一个根只有右孩子，是两棵不同的树。也因为位置本身带信息，序列化的时候空位必须写出来，比如用 # 表示空，不然 [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，去掉了 null，恢复时出了什么问题？
去掉空位后，[1, 2] 分不清 2 是左孩子还是右孩子，树形还原不出来。空孩子要写成 # 之类的标记，读的时候按同样顺序消费。
追问 3结点值里可能有逗号和 #，原来逗号分隔、# 表示空的格式还能用吗？
不能，合法的值会被当成分隔符或空位。直接用 JSON.stringify 存结构，或者每个值加长度前缀，旧数据加个版本号区分。
追问 4有人说二叉树都能用数组下标公式存，左孩子 2i + 1、右孩子 2i + 2，对吗？
能存，但只有完全二叉树划算。稀疏的树按位置展开会留大量空槽，一条往右长的链，10 个结点就要 1023 个位置。
# 二叉树的编码实现
30 秒速记
- 结点三件套：
val、left、right，没有孩子统一用null - 层序数组建树：队列放「等着接孩子的父结点」，每个父结点最多消费两个位置
- 判空位写
value !== null，别写if (value)，0和空字符串是合法值 - 递归遍历先处理
root === null；树很深就换显式栈，防止爆栈 - 数据来自接口要防环和共享子结点，否则遍历会死循环或重复处理
JS 里二叉树结点就是一个对象，存三样东西：自己的值，左孩子的引用，右孩子的引用，没有孩子就写 null。 构造函数里 this.left = this.right = null 先预置好，后面往 left、right 上挂结点就能长出一棵树。LeetCode 给的输入一般是层序数组，比如 [1, 2, 3, null, 4]，建树时用一个队列存「等着接孩子的父结点」，每个父结点依次读两个位置。这里有个很隐蔽的坑：判断空位一定要写 value !== null，写成 if (value) 会把值为 0 的结点也当成空的扔掉。
下面用带空位的层序数组构造二叉树。队列保存“下一批需要接孩子的父结点”，输入游标每次最多消费两个位置；null 只表示缺少孩子，数值 0、空字符串等合法值不能用真假判断过滤。
