企业官网建设流程全解析

你正在准备Java面试吗？或者你刚学完数组和链表，正站在“树”这个门槛前面，想知道它到底是个什么东西？这篇文章就是写给这两种人的。树，可以说是Java数据结构里最“值钱”的一块内容：面试必考、工作中绕不开、刷题时能见到各种稀奇古怪的变体。从最基础的二叉树，到让无数人掉头发的红黑树，再到数据库索引背后的B+树，它们全是树这个大家族里的成员。我这里先给你交个底：树不难，难的是没有人帮你把“为什么要这样设计”讲透。

这篇文章我会从纯Java的视角出发，把树的底层概念、经典实现、高频考点和实际场景挨个拆开。你不需要提前掌握什么高深的东西，只要看得懂递归、看得懂简单的类定义，就能跟着我一步步把树这块硬骨头啃下来。要准备面试也好，要补基础也好，这篇文章都能让你少走很多弯路。

1. 树的本质：为什么面试官总爱问树

1.1 树在数据结构里的位置

先想一个问题：数组和链表解决的是什么问题？是一对一的线性关系——一个元素后面跟着一个元素，像排队一样。但现实世界里的关系远没这么简单。公司的组织架构是一对多，文件系统是一对多，网站的导航菜单是一对多。你需要在内存里表示这种“一个父亲多个孩子”的结构，线性结构就束手无策了，这时候就得请出树。

很多人第一节课被树的术语吓到，觉得它很抽象。其实树就是“嵌套的、有层次的链表”——链表每个节点有一个next指针，树里把next拆成了left和right，甚至更多。在Java里，TreeNode就是一个普通类，里面有几个指向同类对象的引用而已。这个概念一旦想通了，后面所有花样都只是在这个基础上加规则。

再往深处看，树之所以无处不在，是因为它天生具备两个优势：一是能表达层次关系，二是通过特定规则排列之后，可以实现极快的查找。第二个优势尤其重要，二叉搜索树、平衡树、B+树全都是冲着“查找速度”去的。你在JDK源码里看到的TreeMap、HashMap的树化、MySQL索引用的B+树，本质上都是在利用树的这个特性。

1.2 树的专业术语：一次性说透

我在面试中问过很多候选人树的基础，发现很多人对“深度”和“高度”傻傻分不清。这里给你一个不会忘的理解方式：深度是从上往下数，根节点深度为0（有的教材是1，以你手头教材为准）；高度是从下往上数，叶子节点高度为0。树的层数是从根开始的第几层，这个基本不产生歧义。

常用术语就这几个：

• 根节点：树的最顶层节点，一棵树只有一个根。
• 叶子节点：没有任何子节点的节点，俗称“叶子”。
• 父节点、子节点、兄弟节点：字面意思，不用特别记。
• 度：节点拥有的子树个数。二叉树的度最多是2。
• 子树：树里的任何一个节点，连同它下面的所有后代，本身也是一棵树。

还有两个容易混的概念：满二叉树和完全二叉树。满二叉树是“每一层都装满”，完全二叉树是“除了最后一层，其他层都满，而且最后一层的节点都靠左排列”。这两个概念在堆排序和数组存储里特别重要，因为完全二叉树可以用数组来存：下标为i的节点，它的左孩子下标是2i+1，右孩子是2i+2，父节点是(i-1)/2。这个性质后面学堆的时候会用到。

1.3 为什么Java没有提供一个“万能”的Tree类

很多Java初学者会有个疑问：List有ArrayList、LinkedList，Map有HashMap、TreeMap，怎么没有“Tree”这样一个现成的树类给你用？

说实话，这是Oracle的“有意为之”。树这个结构本身太泛了——二叉树、多叉树、搜索树、平衡树、Trie树，每种树的操作逻辑完全不同。你没法用一个万能类去覆盖所有场景。所以JDK的套路是：在具体场景里内置具体实现。TreeMap和TreeSet底层就是一棵红黑树（自平衡的二叉搜索树），HashMap在链表长度过长时会自动转成一棵红黑树，你不需要自己造轮子，直接用就行。但一旦涉及自定义的树结构，比如做一个菜单树、组织架构树、Trie树，JDK就不管你了，得自己写TreeNode类。

另外提醒一句，别把数据结构里的树和Linux设备树、Android视图树搞混。Linux设备树是一种描述硬件信息的配置文件格式，Android的View树是UI组件的嵌套结构，它们只是“碰巧借用了树这个名词”，本质上和Java数据结构里的树不是一回事。面试时如果聊到这块，别绕进去。

2. 二叉树与二叉搜索树：最核心的基础

2.1 二叉树节点的Java定义

二叉树是每个节点最多只有两个孩子节点的树。在LeetCode和面试手写代码时，我们用的TreeNode定义基本都是这个：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }

这个类就三个字段：一个存值，两个存指向左右子树的引用。就这么简单。你用new TreeNode(5)就创建了一个孤零零的节点，然后手动把left和right指来指去，一棵二叉树就串起来了。

我见过不少初学者在这卡壳，他们总觉得树是一个“大整体”，必须要有什么特殊语法来创建。其实树就是一个个普通对象通过引用关系串起来的结构，跟链表一模一样，只是每个节点有两个指针而不再是一个。理解到这个层面，你写代码就不会犯怵了。

2.2 二叉搜索树的查找与插入：左小右大

二叉搜索树（BST）的规则只有一句话：对于任意节点，左子树所有节点的值都小于它，右子树所有节点的值都大于它。注意是“所有”，不是“直接孩子”。这规则一出来，查找就变成了“走迷宫时不断根据提示选左还是选右”的过程：

public TreeNode searchBST(TreeNode root, int target) { if (root == null || root.val == target) { return root; } return target < root.val ? searchBST(root.left, target) : searchBST(root.right, target); }

插入的思路和查找基本一致，先找到合适的空位，再把新节点挂上去。这里有个容易犯错的地方：递归插入必须把返回值赋给root.left或root.right，很多人漏掉这一句，导致插入后树没变。

public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (val < root.val) { root.left = insertIntoBST(root.left, val); } else if (val > root.val) { root.right = insertIntoBST(root.right, val); } return root; }

平均情况下，BST的查找、插入时间都是O(log n)，这个“log n”的来源就是每一层都能排除掉一半的方向，跟你翻字典时直接翻到中间然后往前或往后翻一个道理。但请注意我强调了“平均情况”。

2.3 二叉搜索树的删除：面试手撕的高频坎

删除是BST里最麻烦的操作，很多人笔试就挂在它上面。麻烦在哪儿？在于删除一个节点之后，你还要保持“左小右大”的性质。分三种情况：

1. 目标节点是叶子：直接返回null，让父节点的指针指向空即可。
2. 目标节点只有一个孩子：直接让孩子顶上来，返回这个孩子。
3. 目标节点有两个孩子：这个最麻烦。你需要找到一个合适的节点来顶替它。经典做法是找中序后继（右子树里最小的那个节点），把它复制到目标节点位置上，然后再去右子树里删除那个“最小值节点”。

为什么要找中序后继，不找别的？因为中序后继是右子树中最小的节点，它满足两个条件：大于左子树的所有节点、小于右子树里除了它自己之外的所有节点。用它顶替，整棵树的性质不会被破坏。而且中序后继最多只有一个右孩子，删除它又回到了情况1或2。

public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (key < root.val) { root.left = deleteNode(root.left, key); } else if (key > root.val) { root.right = deleteNode(root.right, key); } else { if (root.left == null) return root.right; if (root.right == null) return root.left; TreeNode minNode = findMin(root.right); root.val = minNode.val; root.right = deleteNode(root.right, minNode.val); } return root; } private TreeNode findMin(TreeNode node) { while (node.left != null) node = node.left; return node; }

这段代码你最好亲手在纸上画一棵三层的树，模拟一下删除根节点的流程。我当年就是靠画图把这个操作彻底搞明白的，光看代码很难真正内化。

2.4 BST退化成链表：引出自平衡

BST看似完美，但有一个致命缺陷：如果按有序序列插入，比如1,2,3,4,5,6,7，它会变成一条只有右孩子的“斜树”，这时候查找的复杂度直接退化成O(n)。你想想，那跟线性扫描链表有什么区别？

为了解决这个问题，计算机科学家想出了一条路：想办法让树在插入和删除之后尽量保持“对称”，不能让某一侧越长越倾斜。这条路衍生出了两个明星结构：AVL树和红黑树。这也是JDK里TreeMap和HashMap树化时真正用的东西。接下来我们就看看它们是怎么把自己“掰平”的。

3. 平衡的艺术：AVL树与红黑树

3.1 AVL树：严格平衡的“强迫症”

AVL树是第一个被发明的自平衡二叉搜索树。它的规则非常狠：任意节点的左右子树高度差绝对值不超过1。这个高度差被称为平衡因子。一旦插入或删除导致某个节点的平衡因子变成了2或-2，就必须通过旋转来恢复平衡。

旋转有四种标准姿势：

• LL（左左）：在左孩子的左子树上插入导致失衡，对失衡节点做一次右旋。
• RR（右右）：在右孩子的右子树上插入导致失衡，对失衡节点做一次左旋。
• LR（左右）：在左孩子的右子树上插入导致失衡，先对左孩子做左旋，再对失衡节点做右旋。
• RL（右左）：在右孩子的左子树上插入导致失衡，先对右孩子做右旋，再对失衡节点做左旋。

旋转的代码核心就是调整引用关系：

private TreeNode rotateRight(TreeNode y) { TreeNode x = y.left; TreeNode t2 = x.right; x.right = y; y.left = t2; return x; } private TreeNode rotateLeft(TreeNode x) { TreeNode y = x.right; TreeNode t2 = y.left; y.left = x; x.right = t2; return y; }

为什么旋转能恢复平衡，不会破坏BST性质？因为旋转只是调整了树型结构，而左小右大的相对顺序没有变。以右旋为例，x是y的左孩子，旋转后y变成了x的右孩子，这个变化自始至终满足“x < y”，同时t2原本是x的右子树，里面所有节点都大于x且小于y，旋转后t2正好挂在y的左子树上，依然符合BST规则。这就是旋转“不破坏有序性”的根本原因。

3.2 红黑树：面试八股文里的“硬骨头”

红黑树在面试里出现频率极高，但你不用慌。网上把红黑树讲得玄乎其玄，其实大家真正需要理解的是它解决问题的思路，而不是手写完整实现（面试真正让你手写红黑树的情况非常少）。

红黑树在BST基础上增加了颜色标记，用五条性质来约束树的形态：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL空节点）都是黑色。
4. 红色节点的两个子节点必须是黑色（不能出现连续两个红色节点）。
5. 从任意节点到它的每个叶子节点的所有路径上，黑色节点的数量相同。

第5条性质是红黑树平衡的根源。它保证了“最长路径不超过最短路径的两倍”——因为最短路径是全黑路径，最长路径是红黑交替路径，红色不能连续出现，所以黑色节点数相同的情况下，红色最多只能让路径长度翻倍。这种平衡比AVL的“严格高度差不超过1”要宽松，但已经足够把操作复杂度控制在O(log n)。

JDK里的TreeMap就是一棵红黑树。每次put时，新节点默认是红色，然后根据情况和父节点、叔叔节点的颜色做变色或者旋转。为什么新节点是红色？因为插入红色节点不容易破坏第5条性质（黑色节点数量不变），如果插入的是黑色节点，那路径上的黑色节点数直接不一样，情况更麻烦。这个逻辑很像“先给你一个能满足大多数规则的默认答案，再在不满足规则的局部慢慢修”。

HashMap里也有红黑树的身影：当单个桶的链表长度超过8、且数组容量不小于64时，链表会转成红黑树；当节点数减少到6时，红黑树会改回链表。8和6之间留了缓冲，避免频繁转换带来的性能抖动。这个阈值是怎么来的？源码注释里给了一个泊松分布的计算，大意是负载因子0.75时，单个桶里链表长度超过8的概率极低，如果真超过8，说明哈希函数分布异常，这时候转红黑树来兜底。

3.3 AVL和红黑树怎么选：一张表说清

面试常见追问是“HashMap为什么不直接用AVL树”。答案的核心在于操作成本。AVL树的查找确实更快，但插入删除的旋转次数更多，因为它的平衡约束太严格，稍微一折腾就要转；红黑树的平衡约束宽松，旋转次数少，整体插入删除性能更稳定。JDK选择的不是“某个操作最快”，而是“所有操作综合下来最优”。

我给个更直白的类比：AVL像完美主义者，每个细节都要对齐，代价是操碎了心；红黑树像“差不多先生”，规则只要不越界就行，代价是整体稍微松散一点，但省心。HashMap选择红黑树，就是看中了它在频繁增删场景下的综合性价比。

4. 进阶树结构：B树、字典树、哈夫曼树与表达式树

4.1 B树与B+树：数据库索引背后的树

你搜索“B树”时会看到大量数据库相关的帖子，这两者强绑定。B树是多路平衡查找树，它和二叉树的本质区别是：一个节点可以存储多个key，也可以有多个孩子。为什么数据库要用多路而不学红黑树只用二叉树？因为数据库数据存在磁盘上，磁盘IO慢得惊人。每读一个节点就相当于一次磁盘IO，树越矮，访问次数越少。B树通过“一个节点塞很多key”让树变得又矮又宽，高度可能是两三层，查询一次最多两三次IO，比二叉树动辄几十次IO香多了。

B+树是B树的改进版，也是MySQL InnoDB索引的真实结构。B+树有两个关键特性：所有数据都存在叶子节点，内部节点只存索引；叶子节点之间用链表串起来。这样设计的好处是查询任何一个数据都要走到叶子节点，时间稳定；而且叶子节点有序且相连，做范围查询（比如查所有年龄在20到30岁之间的人）时，只要在叶子链表上顺序遍历就行，不需要来回回溯。

顺带提一下热词里的“梅克尔帕特里夏树（Merkle Patricia Tree，简称MPT）”，它在以太坊里被用来组织账户状态和交易数据。简单说，MPT就是“字典树+默克尔树”的结合体：既能按key高效查找，又能通过根哈希快速校验整棵树的完整性。它和B+树解决的不是一类问题，一个是区块链场景下的防篡改，一个是关系型数据库里的高效查询，但对“组织大量数据”这件事而言，树依旧是最靠谱的方案。

这里也顺便说一句，网上搜“Linux设备树”搜到的东西其实是描述硬件信息的配置文件格式，跟数据结构里的树完全是两码事，学习时别被这个同名概念干扰。

4.2 字典树：敏感词过滤和自动补全

字典树（Trie，也叫前缀树）解决的是“多个字符串的公共前缀复用”问题。它的每个节点不存完整的字符串，而是存一个字符（或者说一个转移状态）。根节点是空节点，从根走到某个标记节点，路径上经过的字符拼起来就是一个完整单词。

Java实现一个面向26个小写字母的Trie非常直接：

class Trie { private Trie[] children = new Trie[26]; private boolean isEnd; public void insert(String word) { Trie node = this; for (char c : word.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix) { Trie node = this; for (char c : prefix.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) return null; node = node.children[idx]; } return node; } }

Trie的时间复杂度很吸引人：插入和查询都是O(单词长度)，跟有多少个单词无关。这在敏感词过滤、搜索框自动补全、IP路由的最长前缀匹配里都很实用。空间上，字符集越大越费内存，比如汉字Trie树每个节点如果存一个数组，会非常浪费，所以工程里通常用HashMap代替定长数组来节省空间。你可以在面试时主动提这点，会让面试官觉得你是真做过东西而不是背过题。

4.3 哈夫曼树：从压缩算法到Java实现

哈夫曼树又叫最优二叉树，它的核心目标是：让出现频率高的字符编码更短，让整体编码长度最短。具体做法是先把每个字符看成一棵只有根节点的树，权值就是出现频率，然后不断从森林里挑两棵权值最小的树合并成一棵新树，新树的权值是两者之和。合并这件事天然适合用优先队列（Java里的PriorityQueue）来做。

这段过程用Java描述就是：

PriorityQueue<TreeNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val)); // 初始化：为每个字符创建一个节点，val为频率，放入pq while (pq.size() > 1) { TreeNode left = pq.poll(); TreeNode right = pq.poll(); TreeNode parent = new TreeNode(left.val + right.val); parent.left = left; parent.right = right; pq.offer(parent); } TreeNode root = pq.poll();

构建完成后，从根出发向左走记0、向右走记1，路径上的0/1序列就是叶子节点对应字符的哈夫曼编码。注意，哈夫曼编码是前缀编码，也就是说任何一个字符的编码都不是另一个字符编码的前缀，这样才能在解码时做到无歧义、不需要分隔符。这个性质正是哈夫曼树的结构带来的——所有字符都在叶子节点上，路径天然不会互相包含。

哈夫曼树的应用远不止文件压缩。JPEG图像压缩、ZIP压缩、视频编码里都能看到它的影子。它的重要性不在于代码多复杂，而在于它展示了“如何用树来建模一个优化问题”。

4.4 表达式树：把算术表达式变成一棵树

表达式树是把一个算术表达式表示成二叉树：叶子节点是操作数，内部节点是运算符。比如表达式(3 + 4) * 5，根节点是*，左子树是+和它的两个叶子3、4，右子树是叶子5。

构建方法很有意思：把中缀表达式转成后缀表达式（比如3 4 + 5 *），然后从左到右扫描，遇到操作数就压栈，遇到运算符就弹出两个节点作为它的左右孩子，再把运算节点压栈。扫描完，栈顶就是表达式树的根。

对这棵表达式树做后序遍历，先左子树、再右子树、最后根节点，你得到的序列正好就是后缀表达式，而计算后缀表达式的过程其实就是从叶子往根一步步收敛求值的过程。做编译器或解释器的朋友看到这里应该会会心一笑，因为这就是语法分析里抽象语法树（AST）的雏形。表达式树的价值在于，它把“运算的顺序”显式地表达成了“树的形态”，你看树结构就能知道先算谁后算谁，而不用再人为地去记运算符优先级规则。

5. 树的遍历与经典算法题：从理解到秒杀

5.1 前中后序与层序遍历：两种层级、两种写法

树的遍历是后面所有算法题的基础。前序、中序、后序三者非常容易混，这里给一个不死记硬背的口诀：“前中后”指的是根节点被访问的顺序。前序就是“根-左-右”，中序就是“左-根-右”，后序就是“左-右-根”。你用递归写的时候只要记住打印根的位置，位置放前就是前序，放中间就是中序，放最后就是后序：

// 前序 public void preorder(TreeNode node) { if (node == null) return; System.out.println(node.val); preorder(node.left); preorder(node.right); } // 中序把println放中间，后序放最后，代码结构完全一样

递归三行代码谁都会背，但面试真正的考察点是非递归写法——用栈模拟系统递归过程。前序非递归最直观：一路往左走，边压栈边打印，走到头了弹出栈顶拐到右子树。

Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (!stack.isEmpty() || cur != null) { while (cur != null) { System.out.println(cur.val); // 访问根 stack.push(cur); cur = cur.left; // 不断往左 } cur = stack.pop(); cur = cur.right; // 回到上一层，转向右 }

层序遍历是另一种思路，它不递归顺着子树走，而是借助队列一层一层地往外扩。每轮从队列里取出当前层的所有节点（这里用size记录当前层节点数），处理完再让它们的左右孩子入队，这样就能严格按层次从左到右访问。层序遍历在很多“按层处理”的题目里是标配，比如求二叉树最大宽度、打印成锯齿形。

5.2 树的直径：两次DFS的巧妙解法

树的直径定义为树中任意两个节点之间最长路径上的边数。这道题很经典，因为它有一个反直觉的定理：从任意一个点出发，找到离它最远的点A，再从A出发找到离A最远的点B，那么A到B的距离就是树的直径。这个定理在带权树且权值非负时成立，面试时可以直接用。

实现上，第一次BFS/DFS找到最远点，第二次从最远点再跑一遍，记下最大距离即可。不过在LeetCode上，树的直径还有用“递归计算左右子树最大深度并全局更新”的写法：

int ans = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return ans; } private int depth(TreeNode node) { if (node == null) return 0; int leftDepth = depth(node.left); int rightDepth = depth(node.right); ans = Math.max(ans, leftDepth + rightDepth); return Math.max(leftDepth, rightDepth) + 1; }

核心思路是：经过某个节点的最长路径，等于它左子树的最大深度加上右子树的最大深度。每个节点都算一遍，全树的最大值就是直径。这个是典型的“递归时顺便更新全局答案”的模式，很多树形DP题都是这么玩的。

5.3 最近公共祖先：一道题看懂递归返回值设计

求两个节点的最近公共祖先（LCA）是面试高频题。代码不长，但很多人对着答案看不明白它能“找到最近”的原理：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } return left != null ? left : right; }

理解这个递归的关键是搞清返回值语义：它返回的是“以当前节点为根的子树里，已经找到的p或q或它们的公共祖先”。如果左右子树的查询结果都不为空，说明p和q分别位于左右两侧，那么当前节点就是它们的最近公共祖先；如果只有一侧不为空，就说明两个目标都在那侧，或者那侧已经找到了共同的祖先，直接往上传即可。

我建议你在纸上把一棵树画出来，手动模拟几个用例。比如p在根左子树最深层、q在右子树，你会看到递归一层层往上传递，直到某个节点左右都非空，就返回了。这道题吃透了，你对“递归返回值”这个抽象的理解会上一个台阶。

5.4 树的序列化与反序列化：为什么它是压轴题

序列化反序列化是不少大厂终面题。它要求你实现两个函数：一棵树转成字符串，字符串再还原成原来的树。常见的做法是前序遍历加占位符，null节点用特殊符号表示。

// 序列化：1,2,null,null,3,4,null,null,5,null,null public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); preorderSerialize(root, sb); return sb.toString(); } private void preorderSerialize(TreeNode node, StringBuilder sb) { if (node == null) { sb.append("null,"); return; } sb.append(node.val).append(","); preorderSerialize(node.left, sb); preorderSerialize(node.right, sb); }

反序列化时，把字符串按逗号拆开，从左到右重建。前序遍历的顺序天然保证：先重建根，再重建左子树，再重建右子树。遇到"null"就返回空节点。整个逻辑用递归写起来很简洁，前提是你真正理解了前序序列在数组展开后的顺序规则。

序列化反序列化之所以是压轴题，是因为它综合考察了你对遍历顺序的理解、对递归的理解、对边界条件的敏感度。如果你能把这道题干净利落地写出来，面试官基本就认可你的树基础了。

6. 常见问题与排查技巧实录

6.1 递归爆栈与StackOverflow

递归是树题最自然的写法，但有个隐患：如果树的深度非常大（比如链式退化的BST，深度等于节点数），递归层数过多就会栈溢出，报StackOverflowError。这种情况在本地测试还好，在线上或者极端用例里就可能翻车。

解决思路有两个。一是改用显式栈的迭代写法，自己在堆上模拟递归过程，不再依赖系统调用栈；二是优化递归逻辑本身，比如求深度时用尾递归（Java对尾递归没有优化，实际帮助不大），或者像后序遍历那样用Morris遍历把空间压到O(1)。Morris遍历的原理是利用空指针做临时线索来回溯，理解成本偏高，面试时能说出思路就是加分项，不要求一定手写出来。

什么时候用递归，什么时候用迭代？我给你一个实用判断标准：如果树是平衡的或你确定深度不会太大，递归更清晰、代码更好维护；如果题目场景是极端不平衡的“链表树”，或者你做了深度限制但上限很低，那就用迭代。

6.2 空指针、边界条件与其他“低级错误”

刷树题最容易翻车的地方不在思路，而在空指针。我总结了几条血泪经验：

• 任何递归入口都要先判断根节点是否为null。漏掉这个，节点个数为0的用例直接挂。
• 访问node.left或node.right之前，先确认node本身不是null。很多错误都是一拿到节点就往下钻，却不考虑null。
• 求深度、求平衡因子这类题，递归返回值的默认情形要想清楚。返回0还是返回-1指的是不同约定，别混。
• 如果用全局变量记录答案（比如上面的树的直径），多组测试用例之间要记得重置。LeetCode这类在线判题平台一个方法对应一次调用，但如果你自己写测试代码循环跑多个用例，全局变量不清零就会出鬼问题。

你还可能碰到一个隐蔽问题：递归函数返回类型设计得不对。比如判断一棵树是否对称，很多人想着返回boolean，但里面需要比较两个节点，返回值就想不清楚了。这时候把函数签名改成isMirror(TreeNode left, TreeNode right)，递归结构会清晰很多。卡壳的时候先停下来检查自己递归函数的入参和返回值语义是否自洽。

6.3 面试时怎么答树相关的题：我的三个心得

先别急着动笔写代码。面试官问“讲讲红黑树”，你不要上来就背五条性质，可以先说一句“红黑树是一种自平衡的二叉搜索树，核心约束是黑色节点数量在每条路径上保持一致，所以我用颜色和旋转来维护这个约束”，这比直接机械背性质更有条理，也让面试官觉得你理解的是设计思想。

问“HashMap为什么用红黑树”时，把话题引向“8和6阈值”和“泊松分布”往往是加分点。你不一定算出准确概率，但至少要知道：负载因子小于0.75的情况下，链表长度超过8的概率极小，一旦出现说明输入严重冲突，红黑树是兜底方案；6和8之间的1个节点差距是为了防止频繁转换。

最后一点：树的题别光刷不练。我个人的建议是，LeetCode的树专题从二叉树前中后序遍历开始，再到最大深度、直径、最近公共祖先、序列化，这10来道题吃透，大部分树的面试题你都能对付。脑内跑递归不如在纸上画树、手动模拟递归栈，画着画着你就会发现，树没有你想象中那么难。

最后再分享一个小技巧：我在学树的初期，总喜欢把递归调用过程写成注释，比如在preOrder(root.left)上方写“处理左子树这颗子问题”。这个习惯让我很快建立了“递归 = 直接信任子问题已经解决”的思维模式。刷树题卡住的时候，别死磕细节，回到“当前节点要做什么、子问题要返回什么”这两问上，很多题目就通了。