讲解
二叉树是每个节点最多两个孩子的树形结构，它是算法题的半壁江山——树天然递归（每棵子树还是一棵树），递归三要素在这里用得淋漓尽致。写树的递归有一个万能自问：「假设左右子树已经给出正确答案，我怎么组合出本层的答案？」最大深度 = 1 + max(左深, 右深)，就是这么一句话。
三种深度优先遍历的区别只在「访问根」的位置：前序（根-左-右）适合复制树、序列化；中序（左-根-右）在二叉搜索树上产出升序序列——这是 BST 一章反复利用的性质；后序（左-右-根）适合「先处理完孩子再处理自己」的场景，如求高度、删除树。递归写法三行代码，但面试常考迭代写法：用栈模拟调用栈，中序迭代的套路是「一路向左压栈到底，弹出访问，转向右子树」。
层序遍历（BFS）用队列按层展开：每轮循环先记录当前队列长度 size，只处理这 size 个节点——它们是同一层；处理中把下一层入队。这个「size 快照」技巧是层序遍历的灵魂，少了它层与层就混在一起。BFS 一章还会看到它在图上的推广。
另一个实用技能是从层序数组建树（LeetCode 的输入格式）：用队列维护「等待孩子的节点」，按顺序两两分配左右孩子。掌握它，你就能用普通数组快速构造测试用例，本章示例就是这么验证的。
示例
建树工具 + 前序递归 + 中序迭代 + 层序 + 最大深度，一套走完：
import assert from 'node:assert/strict';
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 按层序数组建树，null 表示空位
function buildTree(levelOrder) {
if (levelOrder.length === 0 || levelOrder[0] === null) return null;
const root = new TreeNode(levelOrder[0]);
const queue = [root];
let i = 1;
while (queue.length > 0 && i < levelOrder.length) {
const node = queue.shift();
if (i < levelOrder.length && levelOrder[i] !== null) {
node.left = new TreeNode(levelOrder[i]);
queue.push(node.left);
}
i++;
if (i < levelOrder.length && levelOrder[i] !== null) {
node.right = new TreeNode(levelOrder[i]);
queue.push(node.right);
}
i++;
}
return root;
}
function preorder(root) {
const out = [];
function go(node) {
if (node === null) return;
out.push(node.val); // 根
go(node.left); // 左
go(node.right); // 右
}
go(root);
return out;
}
// 中序迭代：一路向左压栈，弹出访问，转右
function inorderIterative(root) {
const out = [];
const stack = [];
let cur = root;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
out.push(cur.val);
cur = cur.right;
}
return out;
}
// 层序：每轮先快照队列长度，只处理本层
function levelOrder(root) {
if (root === null) return [];
const out = [];
const queue = [root];
while (queue.length > 0) {
const size = queue.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
out.push(level);
}
return out;
}
function maxDepth(root) {
if (root === null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
const tree = buildTree([3, 9, 20, null, null, 15, 7]);
assert.deepStrictEqual(preorder(tree), [3, 9, 20, 15, 7]);
assert.deepStrictEqual(inorderIterative(tree), [9, 3, 15, 20, 7]);
assert.deepStrictEqual(levelOrder(tree), [[3], [9, 20], [15, 7]]);
assert.strictEqual(maxDepth(tree), 3);
console.log('二叉树遍历示例全部通过');
把这棵树画出来对照输出：3 是根，左孩子 9（叶子），右孩子 20（带 15 和 7）。前序先根所以 3 打头；中序在 BST 上会是升序（下一章验证）；层序的 [[3],[9,20],[15,7]] 正是「size 快照」分出的三层。
常见坑
- 层序忘记 size 快照：直接 while 队列非空、碰到就处理，会把不同层混进同一个数组。
- 迭代中序的转向写错：弹出后必须 cur = cur.right（可能为 null，交给外层循环判断），漏了这步右子树整片丢失。
- 递归基准情形漏写：树的递归基准几乎都是 node === null，忘了就栈溢出。
- 以为树只能从根开始想：很多题（如最近公共祖先、路径和）需要「自底向上」回传信息——递归返回值就是回传的通道。
- 建树时孩子分配串位：层序数组里每个等待节点按顺序领两个孩子，i 的推进要精确，建议先画小例子验证 buildTree。
小结
二叉树 = 递归结构；前中后序看根的位置，迭代用栈模拟；层序用队列 + size 快照；层序数组建树让测试用例可快速构造。下一章给二叉树加上序约束：二叉搜索树。