1. 树形结构为什么是面试“钉子户”：家族的演进路线与考察意图
如果你刷过一段时间的算法题，应该会有这种感觉：链表、数组这类线性结构是热身，图论是压轴，而树恰好卡在中间——它既考察递归思维，又能延伸到搜索、动态规划、系统设计。面试官爱考树，根本原因在于树模型能同时探出候选人的三块底子：基础概念是否扎实、递归和迭代能力是否过关、能不能把数据结构知识映射到真实业务场景里。
先说树的家族演进。所有树形结构都有一个共同起点：节点（Node）和边（Edge），根节点唯一，每个节点有零到多个孩子，没有环。在这个基础上演化出二叉树、二叉搜索树、平衡树、B 树、Trie、堆等。面试里问“树的演进”，本质上是问：每一种新结构，是在解决旧结构的什么痛点？
- 二叉树：解决了“多叉树存储和遍历复杂度不可控”的问题，两个孩子让左右分支天然形成分治结构，几乎所有递归模板都基于二叉树展开。
- 二叉搜索树（BST）：在二叉树基础上加上左小右大的约束，让查找、插入、删除的平均复杂度降到 O(log n)。但它有一个致命软肋：插入有序序列时会退化成链表，复杂度直接掉到 O(n)。
- 平衡二叉树（AVL）：通过旋转把左右子树高度差限制在 1 以内，解决了 BST 的退化问题。代价是每次插入和删除后的旋转调整成本偏高。
- 红黑树：把“严格平衡”放宽为“近似平衡”，最长路径不超过最短路径的两倍，用更少的旋转代价换更高的写入效率。所以 Java 的 TreeMap、TreeSet 以及 HashMap 链表转红黑树都选它，而不是 AVL。
- B 树 / B+ 树：解决的是磁盘 IO 场景下的问题。二叉树节点只能存储一个键，树一高就要多次访盘；B+ 树把大量子节点聚合在一个节点上，降低树高，同时叶子节点用指针串成链表，天然支持范围查询。
- Trie（字典树）：用公共前缀压缩字符串存储，是自动补全、敏感词过滤、IP 路由表的底层基础。
- 堆：本质是完全二叉树的数组存储形式，用下标就能定位父子关系，为 TopK、优先队列、堆排序提供服务。
面试官问“演进”，实际上是想听你按“痛点—改进—代价”的主线来回答，而不是背一堆名词定义。
2. 二叉树遍历的底层逻辑：一种模板，递归迭代层序全打通
遍历是树面试题的基本功，也是后面所有题目（LCA、路径、序列化）的基础。很多候选人能默写递归前序遍历，但一让写迭代版本就卡壳，或者把前序中序后序的逻辑记混。问题出在“没理解遍历的本质，只是在背代码”。
2.1 递归遍历：访问时机的艺术
递归遍历二叉树，核心不是“往左走”“往右走”，而是在递归函数的哪个位置访问当前节点。对应代码：
void traverse(TreeNode root) { if (root == null) return; // 前序位置：进入节点时访问 System.out.println(root.val); traverse(root.left); // 中序位置：左子树返回后访问 System.out.println(root.val); traverse(root.right); // 后序位置：右子树返回后访问 System.out.println(root.val); }同一段递归骨架，三种遍历只差“打印放在哪里”。理解这一点后就不会再死记“前序是中左右，后序是左右中”这种口诀，而是从执行时序上推导。
2.2 迭代遍历：显式栈模拟系统栈
递归之所以叫递归，是因为系统帮你维护了一个函数调用栈。迭代版本就是自己用栈模拟这个过程，但要处理好出栈时机的细节。
前序迭代逻辑比较直接：先访问根节点，然后将右孩子入栈，再左孩子入栈（因为栈是后进先出，要先处理左子树）：
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); 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; }中序迭代是很多人的第一道坎。核心思想是“一路向左入栈，弹栈时访问，然后转向右子树”：
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); 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; }注意这个 while 循环的外层条件是cur != null || !stack.isEmpty()，少了cur != null这个条件，根节点只有右子树的场景就会漏掉。
后序迭代是三种里面最绕的。一个技巧是：前序是“中左右”，后序是“左右中”，后序逆序就是“中右左”。所以可以先做“中右左”的遍历，再把结果反转。实现上只需要把前序遍历的左右入栈顺序换一下，最后Collections.reverse(result)。
另一个更通用的方案是用prev指针标记上一次访问的节点，判断右子树是否已经处理完：
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root, prev = null; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.peek(); if (cur.right == null || cur.right == prev) { result.add(cur.val); stack.pop(); prev = cur; cur = null; } else { cur = cur.right; } } return result; }这个版本理解成本高一些，但它直接体现了后序遍历“左右子树都处理完才访问根”的本质。面试时如果时间允许，建议优先讲反转法，简单清晰；被追问再展开 prev 指针版本。
2.3 层序遍历：队列的尺寸分批
层序（BFS）用的是队列而不是栈，关键操作是在每次循环开始时先记录当前队列的大小，这一批全部是同一层的节点：
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> queue = new ArrayDeque<>(); 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; }size一定要在循环外先取出来，如果写成for (int i = 0; i < queue.size(); i++)，队列在循环过程中不断入队，size 会动态变化，导致同一层节点被拆分到不同的结果列表里。这是我见过最多人踩的坑。
层序遍历能延伸出的题型很丰富：求每层最大值、层内节点顺序反转、填充每个节点的 next 指针、判断是否为完全二叉树（层序遍历过程中不能出现“空节点后还有非空节点”的情况）。核心都是“按层分批”。
提示：面试里如果问“递归深度可能导致的栈溢出怎么处理”，答案是两层：一是把递归改成显式栈的迭代写法，二是如果数据规模确实很大，可以考虑 BFS 或者从数据结构层面换思路，比如用数组存储的堆结构或者莫里斯遍历，后者能把空间压到 O(1)。
2.4 莫里斯遍历：O(1) 空间的“加分项”
莫里斯遍历（Morris Traversal）利用叶子节点的空指针来记录线索，遍历过程中能实现不用栈也不用递归，空间复杂度 O(1)。核心逻辑是：当前节点有左子树时，找到左子树的最右节点，把它的右指针临时指向当前节点，形成一个临时环。这样在遍历左子树结束后，能顺着线索回到当前节点继续遍历右子树。
这个知识点面试中不算高频，但属于“提一嘴立刻加分”的内容。你不需要现场完整实现，能把思想说清楚就超过大部分候选人。实际生产环境中基本不会用它，因为会临时修改树的结构，多线程场景容易出问题，它更多是算法竞赛和高级面试里的思维体操。
3. 遍历序列还原二叉树：构造题背后的分治与哈希优化
面试题里有一类常考题：给你两个遍历序列，让你还原整棵二叉树。最典型的组合是“前序 + 中序”和“后序 + 中序”。这类题考察的是你对遍历序列特征的把握：前序/后序负责定位根，中序负责切分左右子树。
3.1 前序 + 中序为什么能唯一确定
前序遍历序列[根, 左子树... , 右子树...]，第一个元素一定是根。拿到根之后，去中序序列里找根的位置，中序中根左边是完整的左子树序列，右边是完整的右子树序列。于是左右子树的长度确定了，回到前序序列中自然就能切出左子树和右子树的遍历序列。递归地对两个子树做同样操作，二叉树就唯一还原了。
这里必须强调一个结论：前序 + 后序不能唯一确定二叉树。因为前序和后序只能告诉你根是谁，但无法区分左右子树的分界点。只有带中序的序列组合才能区分左右部分。顺带一提，如果题目给的是二叉搜索树的“前序 + 只知道是 BST”这个条件，反而可以唯一确定，因为中序就是排序后的结果，等于隐含了中序序列。
3.2 递归实现的完整代码
用前序 + 中序还原树，关键优化是用 HashMap 预存中序序列中每个值对应的下标，让切分操作从 O(n) 降到 O(1)：
public TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer, Integer> indexMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { indexMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, indexMap); } private TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight, Map<Integer, Integer> indexMap) { if (preLeft > preRight) return null; int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int rootIndex = indexMap.get(rootVal); int leftSize = rootIndex - inLeft; root.left = build(preorder, preLeft + 1, preLeft + leftSize, inorder, inLeft, rootIndex - 1, indexMap); root.right = build(preorder, preLeft + leftSize + 1, preRight, inorder, rootIndex + 1, inRight, indexMap); return root; }这里面最容易出错的地方是区间边界的计算。我的习惯是先算leftSize = rootIndex - inLeft，它是左子树节点的数量，然后以它为基准推导前序区间：左子树是[preLeft + 1, preLeft + leftSize]，右子树是[preLeft + leftSize + 1, preRight]。先算大小再算区间，边界就不容易乱。
后序 + 中序的做法几乎一样，只是根从后序遍历的最后一个元素取，递归顺序变成先构造右子树再构造左子树，其余逻辑相同。
3.3 从数组构造：完全二叉树的下标规律
除了从遍历序列还原，还有一种送分题是给你一个数组（通常是层序遍历结果），让你构造成完全二叉树或堆结构。本质是用下标关系建模：数组下标 i 对应的节点，父节点是(i - 1) / 2，左孩子是2 * i + 1，右孩子是2 * i + 2。堆排序、优先队列的底层都是这个模型。
这个规律在“判断是否为完全二叉树”“求某个节点的祖先/后代”这类问题里也常用。面试时候不一定要真的构建一棵树，用数组下标模拟也能通过，这样空间占用更小。
3.4 树的序列化与反序列化：本质也是构造
树的序列化（比如“给定一棵树，编码成一个字符串”）和上述构造题是逆过程。常见做法是前序遍历 + 空节点标记，下面会在专门章节展开。这里先记住一个结论：没有空节点标记的前序遍历字符串不能唯一定义一棵树，因为无法区分左右子树的边界。
4. 路径类题目的解题套路：从深度累加延伸到最大路径和
路径类题目是树面试题的大头，覆盖题型包括求深度、路径总和、二叉树直径、最大路径和等。表面看各不相同，但指导思想高度统一：后序遍历 + 递归返回值携带子树的聚合信息，全局变量记录跨子树的最终答案。
4.1 深度的两种定义与实现
最大深度（Height）的递归式几乎是树的入门第一题：
public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }最小深度的坑在于：不能直接写成1 + Math.min(minDepth(root.left), minDepth(root.right))。因为如果某个子树为空，其深度为 0，会被 min 取到，导致结果是 1——但根节点只有左子树时，最小深度应该是左子树的深度 + 1，而不是 1。正确写法是：
public int minDepth(TreeNode root) { if (root == null) return 0; if (root.left == null) return 1 + minDepth(root.right); if (root.right == null) return 1 + minDepth(root.left); return 1 + Math.min(minDepth(root.left), minDepth(root.right)); }深层原因：深度定义是“从根到最近叶子节点的路径上节点的数量”，叶子节点的左右孩子都为空，不能把空子树当成深度 0。这个题价值不在于难，而在于考察你考虑边界条件的习惯。
4.2 二叉树直径：跨左右子树的路径
二叉树直径是“任意两个节点之间最长路径的边数”。注意这条路径不一定经过根节点，所以不能简单求左右子树深度之和再取最大。正确做法是在递归过程中，每个节点处计算“左子树深度 + 右子树深度”，用它更新全局最大值，同时向上返回“当前子树的最大深度”供父节点使用：
class Solution { int diameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return diameter; } private int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(node.right); diameter = Math.max(diameter, left + right); return 1 + Math.max(left, right); } }这里的代码模式会反复出现：递归函数不仅返回给上层需要的信息，还在过程中悄悄更新一个全局答案。解决“最大路径和”“最长同值路径”“二叉树最大宽度”都是同一个套路。
4.3 路径总和与所有路径
“是否存在一条根到叶子的路径，路径上节点值之和等于 target”，可以用 DFS 减法的思路一路减下去，到叶子节点时判断剩余值是否等于当前节点值。用增加法记录累计和也行，但减法有个好处是无需额外定义累加变量，参数直接传剩余值。
“输出所有路径”则需要在回溯时维护路径字符串，核心是递归进入左子树/右子树前把当前节点值拼入 path，返回后要撤销拼接。撤销的逻辑在字符串场景中可以用一个List<String>存所有结果，然后每次递归传入新的拼接结果来避免显式回溯：
public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); if (root == null) return result; dfs(root, "", result); return result; } private void dfs(TreeNode node, String path, List<String> result) { if (node.left == null && node.right == null) { result.add(path + node.val); return; } if (node.left != null) dfs(node.left, path + node.val + "->", result); if (node.right != null) dfs(node.right, path + node.val + "->", result); }字符串的不可变性让每次递归自动拥有独立的 path，省去了手动撤销的步骤。如果改成StringBuilder做拼接，就必须在递归返回后删除本次追加的片段，否则会串到另一条分支里。
4.4 最大路径和：递归返回值和最终答案为什么不是同一回事
这道题（LeetCode 124）是路径类题目中区分度最高的一道。题目要求：路径可以从任意节点出发到任意节点，至少包含一个节点，求路径上节点值之和的最大值。
关键点在于，一棵子树内部能形成的“最大路径”可能是拐弯的（从左子树的某个节点上来，经过当前节点，再拐到右子树的某个节点下去），但这条拐弯路径不可能再向上接入父节点，因为路径不能分叉。所以递归函数返回值只能代表“从当前节点向下出发的最长单臂路径”，而全局最大值可以在每个节点处比较一次“左臂 + 右臂 + 当前值”。
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { oneSideMax(root); return maxSum; } private int oneSideMax(TreeNode node) { if (node == null) return 0; int left = Math.max(0, oneSideMax(node.left)); int right = Math.max(0, oneSideMax(node.right)); maxSum = Math.max(maxSum, left + right + node.val); return Math.max(left, right) + node.val; } }注意这里对负值子树的处理：Math.max(0, xxx)表示如果某棵子树的贡献是负数，就不选它，相当于路径从当前节点直接开始。遇到树中权重为负数的情况，第一次写这题容易在这里踩坑。深刻理解“单臂返回值”和“全局拐弯答案”的关系，对做所有树形 DP 题都有帮助。
5. 树的最近公共祖先与序列化：两个高频考点的完整解法
5.1 最近公共祖先（LCA）的两种情况
最近公共祖先题目有两个版本：普通二叉树的 LCA 和二叉搜索树的 LCA。前者普适性强，后者能用搜索树性质优化。
普通二叉树的递归解法非常优雅：递归查找左右子树，如果某个节点的左子树中同时找到 p 和 q，或右子树中同时找到 p 和 q，那么它的父辈才是答案；如果 p 和 q 分别出现在某个节点的左右子树中，该节点就是 LCA；如果一个节点本身的值等于 p 或 q，那它也是自己的祖先。
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; }这个实现实际上是在做一次后序遍历：先递归处理左右子树，再判断当前节点能否作为答案返回给上层。很多候选人看懂代码后有个疑惑：为什么root == p || root == q就直接返回？因为如果当前节点是 p，那么 p 的最深祖先一定是自己，继续向下递归已经没有意义；q 如果也在 p 的子树里，p 就是 LCA。
普通二叉树也可以用哈希表存父指针解决：先 BFS/DFS 遍历一遍树，把每个节点的父节点记录到 Map 中；再沿着 p 的父指针链把祖先节点全部标记到 Set 里；最后沿着 q 的父指针链向上找，第一个出现在 Set 中的节点就是答案。这个方案的优势是代码逻辑直白，缺点是空间占用更高。
BST 版本的 LCA 更简单：利用左小右大的性质，从根节点开始比较节点值与 p、q 的关系——如果 p 和 q 都小于当前节点值，答案在左子树；都大于则去右子树；一大一小则当前节点就是 LCA：
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (root.val > p.val && root.val > q.val) root = root.left; else if (root.val < p.val && root.val < q.val) root = root.right; else return root; } return null; }这个版本的复杂度是 O(h)，h 是树高。面试官看到你能区分两套解法，就知道你不仅会背代码，还理解不同数据结构的性质差异。
5.2 二叉树的序列化与反序列化
序列化题目的完整名字是“二叉树转字符串 + 字符串还原二叉树”（LeetCode 297 是典型代表）。核心难点在于没有空节点标记时无法区分叶子节点和缺孩子的内部节点，所以常规做法是前序遍历时在叶子节点的空孩子位置放入一个特殊标记（比如"#"），用逗号分隔每个节点值。
序列化代码：
public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); if (root == null) { return "#"; } sb.append(root.val).append(","); sb.append(serialize(root.left)).append(","); sb.append(serialize(root.right)); return sb.toString(); }反序列化的核心是把字符串按逗号拆分成数组，然后按照前序遍历的顺序，逐个消费数组元素来重建节点。这里有一个细节：数组是共享的，必须用一个可变的全局 index 或队列来记住“当前消费到哪个 token”，否则递归过程中无法正确推进：
public TreeNode deserialize(String data) { Queue<String> queue = new ArrayDeque<>(Arrays.asList(data.split(","))); return build(queue); } private TreeNode build(Queue<String> queue) { String val = queue.poll(); if (val.equals("#")) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = build(queue); node.right = build(queue); return node; }队列的 poll 操作天然承担了“消费一个 token”的职责，而且前序遍历的消费顺序正好满足递归重建的读取顺序：根节点先出队，然后递归消费左子树的 token，注意这里的重点是左子树先消费完（包括空标记），接着右子树的 token 才被消费。用Queue比维护全局 int 下标更不容易出错。
层序序列化（BFS）也能实现同样的效果，只是在反序列化时需要同时维护一个队列记录待挂接孩子节点的父节点。常见面试追问有：能不能把序列化的结果变成自描述结构（比如带上节点数量）？压缩率如何？这些属于加分项，核心逻辑不变。
6. 场景题里的树形结构：组织架构、菜单权限与数据库索引怎么设计
树不只是解题用的抽象模型，在真实系统里到处都是。面试环节后半段经常会出现这类问题：设计一个组织架构树，或者问 MySQL 为什么用 B+ 树做索引。这类题没有标准算法答案，考察的是你把树结构与业务、存储、性能约束结合的能力。
6.1 组织架构树与菜单树的存储方案
最常见的实现方式是把树扁平化存储到一张表里，每条记录带一个parent_id字段。查询全树时一次性加载所有记录，在内存中用Map<Long, List<Node>>按父 ID 分组，然后从根节点往下递归组装，得到完整树。
前端权限菜单树是同一个模型：后端返回扁平列表，前端用一个 Map 把节点按 id 存好，再遍历一次把所有子节点挂到对应的父节点下，最后筛选出根节点列表。这道“扁平数组转树”是前端高频题，Java 里实现核心逻辑如下：
public List<TreeNode> buildTree(List<TreeNode> nodes) { Map<Long, TreeNode> map = new HashMap<>(); for (TreeNode node : nodes) map.put(node.id, node); List<TreeNode> roots = new ArrayList<>(); for (TreeNode node : nodes) { TreeNode parent = map.get(node.parentId); if (parent == null) { roots.add(node); } else { if (parent.children == null) parent.children = new ArrayList<>(); parent.children.add(node); } } return roots; }这段代码有个隐藏前提：所有节点 id 不重复，且父节点一定存在（或 parentId 为根标记）。如果存在孤儿节点（父 ID 指向不存在的记录），就会全部被当成根节点，接口出现多个根——这在排错时是一个很隐蔽的坑。
如果业务需要频繁查询某棵子树下的所有节点（比如统计部门总人数、删掉部门时级联删除），parent_id + 内存递归的方式就效率不高，这时候可以考虑左右值编码（嵌套集模型）：给每个节点分配lft和rgt两个值，左值小于所有后代，右值大于所有后代，查询子树只需要一条 SQL：WHERE lft BETWEEN ? AND ?，代价是增删节点时要整体平移某段区间，适合读多写少的组织架构场景。
6.2 文件目录树与递归统计
文件系统天然是一棵多叉树，面试题“统计某个目录下所有文件的总大小”就是树形 DFS 的实战变体。需要注意不能用简单的深度优先累加文件大小来代表目录大小，因为目录本身还可能包含子目录的空文件夹；用后序遍历的思路，先统计子文件，再汇总返回给父目录，和前文提到的“后序遍历 + 返回值聚合”如出一辙。
真实业务中还要担心符号链接（Symbolic Link）导致的循环引用。处理方案是维护一个已访问的路径集合，遇到重复路径跳过，相当于给递归加了“访问标记”，这和图中环的检测逻辑是相通的。
6.3 数据库索引里的 B+ 树和红黑树
数据库索引选 B+ 树而不是红黑树，核心原因是磁盘寻道的代价远大于内存比较运算。B+ 树的一个节点能存几百到上千个键，高度基本在 3~4 层，查询任何数据最多访问三四次磁盘页。红黑树的节点只有两个子指针，层数太深，在磁盘场景下 IO 次数不可接受。
反之，Java 的 HashMap 里用红黑树是因为内存中寻址几乎无成本，树结构越紧凑越有利。面试中遇到“为什么这里用红黑树但数据库用 B+ 树”这类对比题，答题主线是：内存和磁盘的访问成本不同，导致对“单节点容量”的取舍不同。顺带一提，Redis 的 ZSet 用跳表实现有序结构，也是想用概率结构替代严格平衡树，在并发写场景下减少旋转成本——这又是一个“演进”类问题的经典素材。
注意：候选人容易把 B 树和 B+ 树搞混，答题时着重说明 B+ 树的两个关键差异：内部节点不存数据只存索引键（页能容纳更多键，树更矮），叶子节点用指针串成有序链表（区间扫描无需多次回溯父节点）。
6.4 Trie 在业务中的实战应用
如果面试题或项目背景里涉及搜索推荐、输入提示、敏感词过滤，大概率会引出 Trie。实现上可以基于数组存储子节点（固定字符集时寻址快但浪费空间）或 HashMap 存储子节点（不定字符集更通用）。
一个完整的 Trie 插入和查询模板如下：
class TrieNode { Map<Character, TrieNode> children = new HashMap<>(); boolean isEnd = false; } class Trie { TrieNode root = new TrieNode(); public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { node = node.children.computeIfAbsent(c, k -> new TrieNode()); } node.isEnd = true; } public boolean search(String word) { TrieNode node = traverse(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return traverse(prefix) != null; } private TrieNode traverse(String s) { TrieNode node = root; for (char c : s.toCharArray()) { if (!node.children.containsKey(c)) return null; node = node.children.get(c); } return node; } }Trie 面试中常见的优化点是空间压缩：把只有一个子节点的链压缩成一个节点，就是压缩字典树（Radix Tree），它被用在 Linux 内核的路由表和 Redis 的集群槽位查找中。能说出这一层，基本能让面试官确认你的知识范围不局限在刷题层面。
7. 树上答题的经验心得：从“会做题”到“会被面试官认可”
最后聊聊我在实际模拟面试中反复见到的问题，这些经验比任何模板代码都更值得你带走。
第一，永远先定义清楚边界。听到题目先不要急着写代码，确认三件事：树的节点值范围（有没有负数、空节点是不是 null）、深度从 0 还是 1 开始算（影响最小深度和极端情况）、输入是不是二叉搜索树（如果是，很多题都有更优解）。我见过非常多候选人在这上面想当然，导致后续代码在边界测试上一条条挂掉。
第二，先画例子再写代码。给我一个简单的三层树，动手模拟一遍递归过程。面试官期待的是你能用手指追着函数栈走一遍，而不是默写模板。这个习惯能帮你提前发现“返回值更新全局答案的时机”“空节点标记的位置”这类最容易出的细节问题。
第三，复杂度分析要说人话。不要只背 O(n)、O(h)，要能把 h 和 n 的关系讲明白：二叉树在平衡时 h≈log2(n)，退化成链表时 h=n，所以很多递归方案的空间复杂度是 O(h)，最坏情况会栈溢出。面试官听到你能主动补充这一点，通常会认为你的基础功比较扎实。
第四，题目之间要主动串联。做完前序遍历，问自己能不能写后序；写完递归版，问自己能不能改迭代版；做完路径统计，想想能不能把返回值从 int 改成 Pair（比如同时返回深度和最大值）。面试本就是一次沟通，不要怕说出自己的想法，哪怕思路不完全对，也比闷头写代码强得多。
树形结构这套知识体系，从最简单的三行遍历递归，到复杂的树形 DP 和磁盘索引设计，跨度很大，但主线永远是“递归 + 分支”的思维方式。把每一类题背后的决策逻辑吃透，再遇到什么奇怪的树，你都能拆出个一二三来。
