上个月团队做 Java 基础面试，连续几个候选人卡在同一个问题上：写一个二叉树的前序遍历。代码是背下来了，但一问到递归改迭代、为什么中间节点先出栈、极端情况会不会爆栈，就讲不清楚了。这事让我很有感触。二叉树遍历是一道典型的“看着简单、背后全是坑”的题，几乎所有的 Java 数据结构面试题里都有它的身影，包括 HashMap 底层树化、搜索二叉树退化、线索二叉树，归根结底都要回到遍历这一步。这篇博文不打算再铺垫“二叉树是什么”这种基础，直接从底层实现讲起，把四种遍历方式写清楚，并重点分析为什么你写二叉树程序时总是报运行时错误——空指针、栈溢出、死循环，这些我都踩过，下面一次性讲明白。
1. 二叉树的底层形态：Java 对象引用和遍历起点
很多人学二叉树用 C 语言学惯了指针，切到 Java 后总觉得“少了个东西”。其实 Java 把指针藏起来了，对象引用本质上就是指针的受控版本。弄懂这一点，你才能理解为什么二叉树的操作方式在 Java 里是那样写。
1.1 一个节点类到底在内存里放了什么
先看最普通的实现：
public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } }这个类在堆内存里对应一块连续的内存区域，里面有三个字段：一个 int 值，两个指向其他 TreeNode 对象的引用。left 和 right 并不是把子树“嵌入”到当前节点内部，而是存了另一个对象的地址。
所以一颗树本质上就是一连串“地址互指”的对象图：
TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4);这段代码结束后，内存里存在四个独立对象。root 指向 1 节点，1 节点的 left 指向 2 节点，2 节点的 left 指向 4 节点。3 节点有两个 null 引用。
你不需要用 *、-> 这些符号，但 left 字段存的就是地址。这带来一个关键结论：Java 里一切对象操作都是引用操作，传入方法的是引用拷贝，不是对象克隆。写遍历函数时传 root，函数内部改的是这颗树本身。
1.2 引用传递和遍历起点：为什么根节点地位特殊
二叉树没有“前驱指针”，每个节点只能往下找孩子，不能回头找父节点。这意味着你必须持有根节点的引用，否则整棵树就丢了。遍历的起点永远是根，这个设计直接影响所有遍历算法：
- 前序、中序、后序这三种深度优先遍历，都是“从根开始，沿着孩子引用往下钻”
- 层序遍历是从根开始，按层扩散
- 递归遍历是不断把当前节点的 left/right 传给下一层函数
面试里经常让你写一个findDepth(TreeNode root)之类的方法，如果 root 传进去是 null，直接返回 0 还是抛异常？很多人没想清楚 null 的含义。null 在这里代表“不存在的子树”，它是递归的终点，不是错误状态。
我自己记树的遍历时，脑子里永远放着一张内存图：根节点在顶部，每个节点有两条向下的箭头。递归过程就是沿着箭头走，走到 null 再返回。这张图对应到代码上，就是那三行顺序不同的递归语句。
1.3 从数组到二叉树：底层存储形态的差异
数组在内存中是连续的，通过下标访问是“地址加偏移量”的计算；链表在遍历时只能靠 next 引用一个个跳；二叉树则有两个跳转方向。这三种数据结构面试里常被拿来对比，本质区别就在“存储密度”和“访问路径”上。
二叉树这种组织方式的价值在于：它同时具备“方向性”和“层次性”。你可以从根出发，经过固定次数的跳转找到某个节点，平均跳转次数取决于树的高度。如果树退化成一条链，二叉树就退化成链表，复杂度也跟着退化。这个“退化”话题后面讲平衡树时会详细展开，但它也是理解遍历性能的起点。
2. 四种遍历方向的底层逻辑：前中后序和层序各自存在的理由
为什么是前序、中序、后序、层序这四个方向，而不是随便挑几个顺序？因为它们分别对应了不同的实际需求。理解“为什么要存在”比背代码更重要，面试官换一种问法你就绕不过去了。
2.1 三种深度优先顺序的完整定义
先说定义：
- 前序遍历：先访问当前节点，再访问左子树，最后访问右子树（中左右）
- 中序遍历：先访问左子树，再访问当前节点，最后访问右子树（左中右）
- 后序遍历：先访问左子树，再访问右子树，最后访问当前节点（左右中）
这里的“左”和“右”不是常数，而是两个字树的名称。递归函数传出去的是引用：
void preorder(TreeNode node) { if (node == null) return; System.out.println(node.val); // 操作当前节点 preorder(node.left); // 整个左子树 preorder(node.right); // 整个右子树 }三句话，本质上是同一个模板，只是“操作当前节点”这一行放在哪里不同。面试里写这三个递归方法通常三分钟就够，难的是解释清楚为什么中序遍历二叉搜索树会得到一个升序序列。
原因不复杂：二叉搜索树的性质是左子树所有值都小于当前节点，右子树所有值都大于当前节点。中序遍历按“左中右”的顺序，等于先读完左边一堆较小的值，再到中间节点，再读右边一堆较大的值。整体一列出来，就是升序。
2.2 每种遍历的典型应用场景
这四种遍历不是均匀分布的，不同场景有不同的偏好：
| 遍历方式 | 访问顺序 | 典型应用 | 注意点 |
|---|---|---|---|
| 前序遍历 | 中左右 | 树结构复制、序列化、前缀表达式的树形表示 | 第一个访问的一定是根 |
| 中序遍历 | 左中右 | 二叉搜索树排序输出、线索二叉树的中序线索化 | 对二叉搜索树结果是升序 |
| 后序遍历 | 左右中 | 统计子树高度、释放节点资源 | 先处理完孩子再处理自己 |
| 层序遍历 | 逐层从左到右 | 求树宽、判断完全二叉树、按层输出 | 依赖队列而不是递归 |
前序遍历为什么适合做树结构复制？因为你必须先创建当前节点，才能把递归创建出来的左右子树挂上去。这个顺序就是“先造中，再造左，再造右”，正好是前序。序列化同理，先把根的值写入序列，再递归写子树。
后序遍历的场景在 Java 里常见于释放资源和统计。计算二叉树高度时，你要先知道左右子树的高度，才能得出当前节点的高度，这是“左右中”的顺序：
int height(TreeNode node) { if (node == null) return 0; int leftHeight = height(node.left); int rightHeight = height(node.right); return Math.max(leftHeight, rightHeight) + 1; }注意这里height(node.left)和height(node.right)都写在 return 之前，访问当前节点的操作（取 max 加 1）发生在最后，那就是后序。
2.3 线索二叉树：为什么有人要“省掉遍历的栈”
热词里出现“线索二叉树”，这里捎带讲清楚。递归或迭代遍历时，你得用系统栈或自己的栈来记住下一步去哪。线索二叉树的想法是：把节点里空闲的 left/right 引用利用起来，指向遍历顺序中的前驱或后继节点。
中序线索二叉树空出来的 right 指针可能直接指向“中序下一个节点”，这样遍历时就不需要栈了，一路顺着线索走就行。它是个优化思路，面试偶尔会问，核心考点是：让空指针不空着，帮遍历指路。代价是维护线索麻烦，插入删除更复杂。
3. 递归遍历：简洁背后看不见的调用栈成本
递归遍历是二叉树入门的第一道坎。代码确实短，但很多人只记住了写法，没搞清递归发生时 JVM 里发生了什么，导致遇到大树就直接栈溢出。
3.1 一个递归调用里发生了什么
每次调用preorder(node.left)，JVM 会往调用栈里压入一个栈帧。栈帧里保存了当前方法的局部变量、操作数栈、返回地址。递归不特殊，它就是普通方法调用，只不过调用的是自己。
以遍历一棵三个节点的树为例：
preorder(root); // 栈帧F1 -> preorder(root.left); // 栈帧F2 -> preorder(root.left.left); // null，栈帧F3，立即返回 -> preorder(root.left.right); // null，栈帧F4，立即返回 返回F2 -> preorder(root.right); // ...树有多少层，递归调用的最大深度就是多少。如果这是一棵完全平衡的二叉树，高度是 log2(N)，递归深度很温和。但如果树退化成一条链，每个节点只有一个孩子，递归深度就是 N，一万层的链表型二叉树就足以让默认栈大小溢出。
栈溢出是运行时错误里最典型的一种，后面专门有一章讲排查链路，这里先记住一个经验：递归深度约等于树的高度，不是节点数。做笔试时看到 N 的上限，先算算最坏情况高度有多大。
3.2 递归三要素不是背的，是防止踩坑的
递归写法有公认的三要素：终止条件、递归调用、子问题划分。停在纸面上没用，我用一个烂例子说明为什么必须过脑子：
void bad(TreeNode node) { if (node == null) return; // 终止条件 bad(node.left); bad(node.left); // 错误：递归了两次左子树 }这个例子是笔试题里常见坑，它不会栈溢出，但会漏掉右子树，而且左子树会被重复访问两遍。逻辑错了，运行时不一定报错，程序“正常”跑完，结果却完全不对。所以写完代码第一件事，不是看有没有异常，而是对着小树把调用过程手推一遍。
我自己刷题和写工具时有个习惯：在递归函数入口打印一行日志，记录当前访问的节点值和方向。小树看不出问题，但一旦节点数上到两位数，日志后面那几行就能暴露递归顺序是不是错了。
3.3 递归线程安全与性能问题
递归还有个很少人提的点：多线程环境下，每个线程栈独立，递归不会互相干扰。但这不是你随便加递归的理由。递归每层都有方法调用开销，函数调用、参数压栈、返回值传递，这些成本在高频调用下会累积。
Java 虚拟机对递归有优化，但远不及尾递归优化常见。用递归遍历十万节点的退化树，StackOverflowError 很容易出现。这不是“递归不好”，是你选错了工具。所以实际项目里，凡是数据规模不确定、最坏深度可能上万的地方，我优先写迭代版本，或者干脆用队列做层序遍历。
4. 迭代遍历手工栈：从系统调用栈换成自己管理的栈
面试里高频追问是“你会递归，能不能不用递归写前序遍历？”考的就是迭代版本。本质是：把你的栈从 JVM 调用栈里搬出来，亲手管理入栈出栈的时机。
4.1 前序迭代：最简单的转换思路
前序迭代代码既短又直观：
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new LinkedList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 先压右再压左，出栈顺序才是先左后右 if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return result; }栈是后进先出。想要访问顺序是“中-左-右”，就必须让左子树后进栈，这样下一轮访问从栈顶出来的是左子树。这个“先右后左入栈”的操作就是整个前序迭代的核心。
很多文章会把这段写成“先访问根，再访问左，最后右”，好像顺序是自然发生的。实际上栈顶永远是刚进去的节点，控制顺序的唯一方法是调整压栈顺序。把两行 push 顺序反过来，访问顺序就变成“中-右-左”了。
4.2 中序迭代：难点在怎么回来
中序迭代比前序麻烦，因为你不可以直接访问根。要先一路向左走到头，访问最左节点，然后再回头处理它的父节点。这个“回头”的动作靠栈保存父节点引用：
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 一路向左，把途中的节点入栈 while (cur != null) { stack.push(cur); cur = cur.left; } // 出栈一个节点，访问它 cur = stack.pop(); result.add(cur.val); // 转向右子树 cur = cur.right; } return result; }这个模式一定要反复手写几次。我第一次转型时总想着一口气写完，结果时常陷入死循环。后来明白了：cur 变量是用来“探路”的指针，stack 是用来“记路”的备忘录。走到 null 不代表结束，栈里还有一堆父节点等着访问。
右子树处理的关键在于：cur = cur.right后，如果右子树是 null，下一次循环不进入内层 while，直接从栈里弹一个节点。那个节点恰好是当前子树的父节点，这个行为等价于递归调用的“返回上一层”。
4.3 后序迭代：两个技巧我推荐先学这个
后序是迭代里最烦的。我早期用“标记法”做，代码里得给节点加访问标记，后来发现一个更简洁的办法：反向建表。
public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); if (root == null) return result; Deque<TreeNode> stack = new LinkedList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.addFirst(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } return result; }这个思路很巧妙：后序是“左-右-中”。如果把访问顺序反过来看，就是“中-右-左”。这正好和前序遍历的“中-左-右”只差一个左右顺序的交换。所以这段代码把前序里的压栈顺序换成“先压左再压右”，出栈顺序变成“先右后左”，再把结果每次 addFirst 插到链表头，最后整体顺序就被反转成后序了。
前序出栈：中 -> 左 -> 右 当前代码出栈：中 -> 右 -> 左 addFirst 后：左 -> 右 -> 中这个技巧省去了标记节点的麻烦，代码量小，面试时容易讲。唯一的注意点是用LinkedList而不是ArrayList，因为 addFirst 操作在数组实现上代价高。
4.4 递归改迭代的通用思路
三种深度遍历转迭代放在一起对比，规律很清楚：
| 遍历 | 关键点 | 常见错误 |
|---|---|---|
| 前序 | 先压右子树，后压左子树 | 压栈顺序写反 |
| 中序 | 一路向左压栈，返回到父节点时转向右子树 | 右子树为 null 时不知道弹栈 |
| 后序 | 反向建表或标记已访问节点 | 忘记反转导致顺序错误 |
核心思路都一样：栈维护“还没处理完的祖先节点”，循环里负责访问一个节点并安排它的孩子入栈。递归里系统帮你做的“记录返回点”，现在你自己用栈记录。
我面试候选人时会追加一个问题：“如果树是一棵 100 万节点的链，递归和前序迭代分别会发生什么？”这个问题逼着他们想到栈深度和内存。递归大概率栈溢出，迭代用显式栈，栈大小由堆决定，同样可能 OOM，但可控性更强。能答出这一点，才算真的理解底层实现。
5. 层序遍历与队列：宽度优先为什么必须用先进先出
深度优先遍历用栈，层序遍历用队列，这不是随手选的，数据结构特性决定遍历策略。
5.1 队列在层序遍历里的不可替代性
层序遍历要求“先处理本层的所有节点，再进入下一层”。如果访问根时把左右孩子放进队列，队列先进先出，下一轮出队的一定是父节点的左孩子，然后是右孩子，正好按层展开。
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; }这里有一个重要的小细节：int size = queue.size()必须在 for 循环之前取。如果直接在i < queue.size()里判断循环条件，队列里会不断加入下一层节点，导致当次层处理到新节点，层次划分就错了。我刚写层序遍历时没注意，结果每层个数不对，调试了半天。
5.2 能解决的问题一眼就能认出来
层序遍历能解决几个标志性问题：
- 二叉树最大宽度：同一层最左节点和最右节点之间的宽度
- 判断一棵树是不是完全二叉树：按层扫描时，只要遇到一个 null 的子树就让标记置位，后续再遇到非 null 节点就说明不是完全二叉树
- 按层打印、按层求平均值，都是同一个结构
Java 里队列实现常用LinkedList，它实现了Deque接口，推入推尾都行。层序遍历只用 offer、poll 两个方法，选它没毛病。热词里提到的“双端队列”在二叉树遍历里也有一席之地，比如锯齿形遍历（之字形遍历）：奇数层从左到右，偶数层从右到左。实现技巧是层序迭代时用ArrayDeque的 addFirst/addLast 按层决定插入方向。
5.3 什么时候该用 BFS 而不是深度遍历
我在实际项目里判断的依据很简单：如果问题是“到根的距离最近的一条路径”“判断是否存在某层满足条件”，优先 BFS，因为 BFS 天然一层层扩散，第一次到达目标节点时路径就是最短的。如果问题是“遍历整棵树做统计算法分析”，深度遍历更自然。
有一道经典题：求二叉树的最小深度。递归写法很容易写成“取左右子树最小高度”，但实际上如果某一边子树为空，最小深度应该取另一边的深度，这是一个很容易错的边界条件。用 BFS 写最小深度就没有这个歧义：按层扫描，遇到第一个“左右孩子都为 null”的节点，立即返回当前层数，天然正确。
6. 写二叉树程序时为什么总是报运行时错误的完整排查链路
热词里有一个搜索量很高的疑问：“写二叉树程序时为什么总是报运行时错误”。这个问题我太有共鸣，几乎每个学二叉树的人都会连续踩坑。下面按我的实际排查流程从零到尾讲一遍。
6.1 错误一：空指针异常，别名 NullPointerException
二叉树里空指针出现的频率远高于普通项目。原因无他，树上到处是 null。每个叶子节点的孩子都是 null，如果你访问node.left.val时 node 是 null，立刻就炸。
最容易发生空指针的几个地方：
| 场景 | 错误写法 | 正确写法 |
|---|---|---|
| 递归入口没判空 | int h = height(root.left)在 root 为 null 时执行 | 先if (root == null) return 0 |
| 层序遍历把 null 入队 | queue.offer(root.left)不判断孩子是否为空 | 先if (root.left != null) |
| 返回结果集合未初始化 | 使用 null 的 List 后 add | 提前new ArrayList初始化 |
空指针的排查第一步不是看代码，是看异常栈。Java 的空指针异常会精确告诉你哪个类哪一行报错。你只要打开那一行，看到那一行的访问链上有哪个引用可能是 null，问题就缩小到很小范围。最忌讳的是“感觉在数学上没问题”就反复打印硬币。
我自己排查空指针的固定办法是加保护日志，在传参前打印引用是否为 null：
System.out.println("visit node: " + (node == null ? "null" : node.val));这一步的信息量极大，因为你能看到递归走到哪一步时突然变成 null，从而快速确认是终止条件错误还是子树引用赋值错了。
6.2 错误二：栈溢出，别名 StackOverflowError
栈溢出通常发生在两种情况下。
第一种是递归深度过大。树的高度本来就高，比如 10 万节点的斜树，递归一万层左右就可能碰到栈上限。你可以看到异常栈里不断重复同一个递归方法名，从下往上密密麻麻。
第二种是终止条件漏写或写错，递归无限循环下去。二叉树本身是有限节点，递归如果每次只走 left，会一路访问到最后 null 吗？不一定。如果你错误地在某个递归分支里没有缩小范围，比如：
void wrong(TreeNode node) { if (node == null) return; wrong(node); // 永远传同一个引用 }这不是二叉树遍历里该出现的事，但手滑确实会写出来。排查时看到 StackOverflowError 且异常栈是同一个方法反复出现，先检查参数是不是每层都变了。
真实场景里，我见过最隐蔽的栈溢出是线程栈大小被环境修改过。默认线程栈大小通常足够递归几千层，如果部署平台把栈调得很小（比如某些容器里 -Xss 设置过低），本来能跑起来的递归突然就溢出了。处理办法有两个：要么调大栈，要么改写迭代版本。
6.3 错误三：逻辑正确但结果不对，问题往往藏在树的构建里
很多“运行时错误”其实不是异常，而是结果偏差。写字二叉树遍历代码之前，你得先有一棵正确的树。笔试刷题平台通常直接给你树的根节点，但实际工程里你常常要自己从数组构建二叉树。
从数组构建一棵树时，最容易踩的坑是按索引直接赋值，但忽略了数组里用 null 代表“这个位置没有节点”。如果数组是[1, null, 2, 3]，直接取 index 3 给 index 1 的右孩子就能配对，但 index 2 是 null，说明 index 1 的左孩子不存在，后面 index 3 不能凭空挂到 null 节点下面。
我自定义了一个简单的工具方法：
public static TreeNode buildTree(Integer[] values) { if (values == null || values.length == 0) return null; TreeNode root = new TreeNode(values[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < values.length) { TreeNode node = queue.poll(); if (values[i] != null) { node.left = new TreeNode(values[i]); queue.offer(node.left); } i++; if (i < values.length && values[i] != null) { node.right = new TreeNode(values[i]); queue.offer(node.right); } i++; } return root; }这个工具是我做本地调试的标配。它按层序构建树，遇到空位就跳过，不会把 null 节点继续展开。凡是写遍历相关的代码，我都先构建几棵小树，把遍历结果手算出来，再对比程序输出。
6.4 一个完整的排查示例
我在本地写过一个小测试，先用上面那个 buildTree 建一棵树[1,2,3,null,null,4,5]，然后跑一个后序迭代代码：
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new LinkedList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } return result; }如果没写 addFirst，直接输出[1,2,3,4,5]，一看顺序就不对。接着我回看代码，发现 result 用了 add 而不是 addFirst，修正后输出[5,4,3,2,1]，但后序期望是[2,4,5,3,1]。再检查压栈顺序，把“先左后右”改成“先右后左”，输出变成正确的后序。整个排查链路就是：用小树验证 → 对比顺序 → 分清反转逻辑 → 检查压栈顺序。
这个例子说明一个通用方法：二叉树遍历的调试不要凭感觉，要把“期望输出”和“实际输出”列出来，逐一比对顺序差异。顺序不同的位置直接指向代码里的压栈顺序或 add 方式，至少能省一半调试时间。
7. 从遍历到平衡树底层：搜索二叉树、AVL 与 HashMap 树化逻辑
很多人以为二叉树遍历学完就算完，其实它是一条主线，贯穿到检索和工程底层。Java 的 HashMap 底层就藏着树化的逻辑，而树化逻辑正是从二叉搜索树的平衡问题延伸过来的。
7.1 搜索二叉树的遍历为什么能排序
二叉搜索树（BST）的定义很简单：左子树所有节点的值小于当前节点，右子树所有节点的值大于当前节点。中序遍历就是升序序列，这个结论前面已经讲过。一个经典的面试追问是“给定一棵 BST，怎么把它改造成一棵递增的链表或累加树？”
累加树的经典题 LeetCode 538 就是用“反向中序遍历”：右-中-左，把每个节点的值累加上去。这也说明中序遍历的变体并不难，只要改变访问顺序方向即可。
7.2 为什么不平衡会出问题
BST 的查找效率取决于树的高度。完全平衡时高度是 log2(N)，每做一次查找最多沿着树走 log2(N) 次。但如果你依次插入有序数据，比如 1,2,3,4,5,6，每次插入都挂在右孩子上，树就变成了一条链，高度变成 N，查找效率从对数级退化到线性级。
这就是 AVL 树和红黑树存在的意义。AVL 树维护一个平衡因子，任何节点的左右子树高度差最多为 1。插入或删除导致不平衡时，就做旋转操作：
- LL 型：对失衡节点做一次右旋
- RR 型：做一次左旋
- LR 型：先左旋再右旋
- RL 型：先右旋再左旋
旋转的目的是把过高的子树抬升一层，把矮的子树降下去，从而保持整个树的高度在 log2(N) 附近。旋转操作的主体其实就是调整孩子引用：
private TreeNode leftRotate(TreeNode node) { TreeNode newRoot = node.right; node.right = newRoot.left; newRoot.left = node; return newRoot; }这几行代码里藏着二叉树遍历的全部底层经验：引用指向改变了，树的结构就变了；返回的 newRoot 要接回上层，否则整棵树中间会断开。很多人在旋转题目里写错，就是因为忽略“旋转后要更新父节点的引用”。
7.3 HashMap 树化为什么选红黑树
Java 8 的 HashMap 底层在单个桶内元素数量超过阈值（默认 8）时，会把链表转成红黑树。这个设计背后其实是从“遍历”出发的权衡逻辑：
- 用链表存冲突元素，查找要走完链表，复杂度 O(N)
- 用红黑树存冲突元素，查找复杂度 O(log N)，树高度是对数级别
- 红黑树是一种弱平衡的二叉搜索树，不需要像 AVL 那样频繁旋转，插入删除更高效
这里面的核心仍然是二叉树遍历的代价问题。链表退化成树链时效率差，树保持平衡时效率高。HashMap 选择红黑树而不是 AVL，是因为 AVL 平衡太严格，插入删除要频繁旋转，工程上红黑树的综合性能更稳。面试被问到 HashMap 底层原理时，从“为什么 8”开始讲树化逻辑，再引出遍历复杂度，通常能被面试官认为你真的有体系概念。
7.4 遍历算法在工程里的延续
很多框架源码里都藏着树的影子。TreeMap 底层是一棵红黑树，它支持按键顺序遍历，靠的正是中序遍历；PriorityQueue 底层是堆，堆可以看成一种特殊的完全二叉树；JVM 的 GC 根扫描也有树状结构的影子。学二叉树遍历不只是为了刷题，它是阅读这些底层源码的基本功。
我自己看 TreeMap 源码时，最省力的方式就是先在纸上画一棵小红黑树，然后把中序遍历结果标出来，再对照源码里的 successor 方法。其实所谓的“继任者”就是中序遍历的下一个节点，从底层逻辑看就是怎么在树里找下一个引用地址。能把遍历顺序讲清楚，再去理解这些源码，很多东西会一下通透。
我个人在实际操作里体会到最深的还是那句老话：二叉树遍历永远先画图。画清楚引用指向、访问顺序、栈和队列的状态变化，代码怎么写都不会跑偏。下次再遇到“写二叉树程序时报运行时错误”，不用慌，请你先低头看看有没有访问 null、有没有写错压栈顺序、有没有构建出错，这三个坑填平，剩下的基本都是功德圆满。
