前几天一个朋友跟我吐槽说在线笔试里碰到了一道“树状结构查询”的题分值200第一眼觉得简单写完却只拿了一部分分数。他把题面发给我我一看就明白问题出在哪这类题真正考的从来不只是“会不会遍历树”而是能不能把一个松散的父子关系列表转换成可以稳定检索的结构并且在不同语言里实现细节完全不一样。这篇文章我会用 Java、JS、Python 各写一版完整实现把建树、遍历、排序、去重、边界处理这些环节全部拆开讲。适合正在准备笔试面试的同学、工作中频繁跟菜单/组织架构/分类树打交道的前后端开发者也适合想系统整理树状结构查询思路的读者。1. 题面还原父子关系输入和一个看似简单的查询1.1 我见过的最常见题面“树状结构查询”在笔试里出现频率极高不同平台会换一点壳但核心结构基本一致我综合一下大概是这样的第一行输入一个整数 n表示有 n 条父子关系。接下来 n 行每行两个字符串 a 和 b表示 a 是 b 的父节点。最后一行输入一个字符串 target表示要查询的节点。要求输出从 target 出发能到达的所有子孙节点按字典序升序排列每行输出一个节点如果 target 没有任何子孙节点则什么都不输出。举个例子5 A B A C B D B E C F A查询节点是 AA 的直接子节点是 B 和 CB 的子节点是 D 和 EC 的子节点是 F所以所有子孙节点是 B、C、D、E、F按字典序排列后输出B C D E F别小看这个例子它能讲清楚 90% 的考点。真正动手写代码时你会发现输入没有按树层序给你排好可能连根节点都有好几个甚至可能出现重复关系和循环关系。1.2 这道 200 分题真正在考核什么很多人以为这题考的是树的遍历其实不够全面。我拆过几套类似的题发现它真正在考核三件事。第一能不能把“边关系”正确转换成可检索的数据结构。输入给你的不是一棵建好的树而是一堆带方向的线。你需要想到用“父节点 - 子节点列表”的邻接表来组织而不是试图定义 TreeNode 类然后手动拼接父子指针。后者在数据以字符串形式自由输入时非常别扭而且很容易漏掉根节点不连续的情况。第二能不能处理重复和环。输入里完全可能出现两次A B如果你不去重输出就会多一个 B。输入也可能出现A B和B A这种循环关系如果没有 visited 集合DFS 会无限递归直接把程序跑挂。很多人在小样例上测得好好的一换大数据就栈溢出或者超时往往就是栽在这里。第三能不能按要求排序。题面要求“字典序升序”我见过有人直接把节点存进 TreeSet 让容器自动排序这个思路本身没问题但需要保证你使用的语言、容器对“字典序”的定义和判题系统一致。尤其当节点是数字字符串时“10”和“2”到底谁在前特别容易翻车。后面讲 JavaScript 实现时我会重点展开这个坑。1.3 核心思路邻接表 DFS/BFS 排序我的解决方案很固定先遍历所有父子关系构建一个父节点 - 子节点列表的映射然后从 target 出发做深度优先遍历DFS或者广度优先遍历BFS每遇到一个子节点就加入结果并用一个集合记录已经访问过的节点防止重复和环遍历结束后对结果整体排序再逐行输出。时间复杂度是 O(n m k log k)其中 n 是输入的关系条数m 是 target 的子孙节点数k 是结果大小。空间复杂度是 O(n)主要花在邻接表、visited 集合和结果列表上。这个复杂度对笔试题目来说已经非常健康了。理解了整体思路后下面进入正题看三种语言分别怎么写以及每种语言里那些“只有自己人才知道”的细节。2. Java 实现从 HashMap 邻接表到一次干净利落的 DFS2.1 可以直接跑的 Java 完整代码Java 版本我推荐用HashMapString, ListString做邻接表用HashSetString做去重用Collections.sort()做字典序排序。完整代码如下import java.util.*; public class TreeQuery { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n Integer.parseInt(sc.nextLine().trim()); MapString, ListString tree new HashMap(); for (int i 0; i n; i) { String[] parts sc.nextLine().trim().split(\\s); tree.computeIfAbsent(parts[0], k - new ArrayList()).add(parts[1]); } String target sc.nextLine().trim(); ListString result new ArrayList(); SetString visited new HashSet(); dfs(target, tree, visited, result); Collections.sort(result); for (String node : result) { System.out.println(node); } } private static void dfs(String node, MapString, ListString tree, SetString visited, ListString result) { for (String child : tree.getOrDefault(node, Collections.emptyList())) { if (visited.add(child)) { result.add(child); dfs(child, tree, visited, result); } } } }这份代码提交到常见的在线判题环境里是可以直接跑的。如果你们笔试平台用的是 Java 17 甚至更高版本computeIfAbsent和getOrDefault都可以放心用如果平台锁的是 Java 8这两个方法也在 JDK 8 里就有了不冲突。2.2 为什么要用 computeIfAbsent 管理子节点列表很多初学 Java 的人构建这种邻接表时会写三行if (!tree.containsKey(parent)) { tree.put(parent, new ArrayList()); } tree.get(parent).add(child);这当然没有错但computeIfAbsent一个方法就能完成同样的事而且更清晰。它的语义是key 不存在时用第二个参数提供的函数生成一个初始值并放入 Map然后返回这个值key 已存在时直接返回旧值。所以tree.computeIfAbsent(parent, k - new ArrayList()).add(child)一行就完成了“取列表没有就建列表然后追加子节点”的完整操作。我不建议在笔试现场手写TreeNode嵌套类再用left/right指针去拼树因为这道题的节点 ID 是字符串真正输入的数据可能是多叉树、森林用二叉树模型不仅不直观还容易把简单问题复杂化。你只需要记住一句话凡是给“点与点的有向关系”让你查子孙的题第一反应都应该是邻接表。2.3 visited 在防重复和防环上的双重作用visited 集合是这份代码里最不能省的部分。第一个作用是防重复输入。判题系统有时会故意在数据里混入重复的父子关系比如A B出现了两次如果你不判重B 会被输出两次格式错误。第二个作用是防环。如果数据里混入了A B和B A从 A 出发的 DFS 会无限循环A - B - A - B……我在代码里用的是if (visited.add(child))这个写法有一个微妙的地方Set.add()在元素不存在时返回 true 并且加入集合在元素已存在时返回 false什么都不做。所以这一句同时完成了“标记已经访问”和“是否继续处理”两个动作。如果拆成先contains再add在高并发场景下可能有竞争问题但在笔试里没关系只是不够紧凑。这里提醒一个容易理解错的地方target 本身要不要预先放进 visited不需要。因为我们的结果集只收集子孙节点target 不可能是自己的子孙。万一数据里有child - target这样的反向边DFS 扫到 target 时visited.add(target)会返回 false这个分支会被自然跳过不会无限递归。2.4 机考里的输入输出细节Scanner 和 BufferedReader 怎么选笔试环境里 Java 最容易被扣分的往往是输入输出而不是算法本身。Scanner 用起来方便但要小心nextInt()不会消费换行符导致后面的nextLine()读到空字符串。我上面代码里全程用nextLine()然后自己trim()和parseInt()这样就不会有换行符残留的问题。如果题目给的 n 很大比如十万条边以上Scanner 逐行读取会比 BufferedReader 慢不少会拖累整个提交的运行时间。我一般这样判断n 在几千级别Scanner 完全没压力n 到十万级别建议换成 BufferedReaderBufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim());输出端还有一个容易被忽略的规则题面说“没有子孙节点则输出空”很多同学会在result.isEmpty()时输出一个空行大多数判题系统不敏感但极少数严格系统会判格式错误。最安全的做法就是什么都不输出让程序直接结束。我的代码里 for 循环天然满足这个要求空结果时不会打印任何东西。3. JavaScript 实现Map、Set 和那个最容易翻车的排序3.1 Node.js 环境下的完整代码JS 版本在笔试里通常跑在 Node.js 环境输入方式绕不开 readline 事件流。完整代码如下const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) lines.push(line.trim())); rl.on(close, () { const n parseInt(lines[0], 10); const tree new Map(); for (let i 1; i n; i) { const [parent, child] lines[i].split(/\s/); if (!tree.has(parent)) tree.set(parent, []); tree.get(parent).push(child); } const target lines[n 1]; const result []; const visited new Set(); const dfs (node) { const children tree.get(node) || []; for (const child of children) { if (visited.has(child)) continue; visited.add(child); result.push(child); dfs(child); } }; dfs(target); result.sort((a, b) (a b ? -1 : a b ? 1 : 0)); for (const node of result) console.log(node); });这套代码我在几个平台的模拟题里都验证过输入处理、建表、DFS、排序、输出一条龙逻辑和 Java 版完全对应。3.2 为什么我坚持用 Map 而不是普通对象前端同学写这种题时第一反应通常是const tree {};然后用字符串当 key。这在绝大多数情况下没问题直到节点 ID 叫constructor或toString。普通对象继承自Object.prototype你访问tree[constructor]时拿到的不是数组而是对象自带的方法后面的.push(child)直接报错。这不是理论上的风险我在本地真的复现过。用Map就彻底绕开了原型链污染问题Map的 key 就是纯粹的字符串不会跟对象原型上的属性混在一起。这个习惯不只是笔试需要写前端业务代码时同样适用凡是拿外部输入当对象 key 的都建议优先考虑Map。另外JS 里Set的去重语义和 Java 的HashSet一致。我代码里用visited.has(child)先判断再标记主要是为了语义清楚。如果你想写得和 Java 版一样紧凑也可以这样if (!visited.has(child)) { visited.add(child); result.push(child); dfs(child); }3.3 排序比较函数字典序和数值序的岔路口这是 JS 版本最阴的坑我专门拿出来说。Array.prototype.sort()如果不传比较函数会把元素转成字符串后按 UTF-16 码元比较看起来好像符合字典序但在数字字符串面前容易让人产生误解。比如节点是10和2不传比较函数时10会排在2前面因为字符1的码元小于2。这其实正是字典序的预期结果可很多同学脑子里的“升序”是数值升序于是手一抖写了sort((a, b) a - b)结果输出变成 2、10跟题面要求完全相反。那用localeCompare行不行我建议机考里别依赖它。localeCompare的行为受 Node 编译时是否包含完整 ICU 数据影响不同环境下的排序结果可能有差异而且它的语义是“按区域设置的自然语言排序”并不等于题目里说的“字典序”。最稳的是自己写比较函数result.sort((a, b) (a b ? -1 : a b ? 1 : 0));这个比较函数对任何字符串都会按码元逐一比较结果和 Java 的Collections.sort、Python 的list.sort()完全一致。如果你只想记住一条规则那就是字符串字典序用这个自定义函数不要用a - b。3.4 异步输入与递归栈溢出的处理JS 的 readline 是事件驱动的逻辑必须放在close回调里执行。我见过有同学在定义rl.on(line, ...)之后立刻for循环去读 lines结果 lines 还没被填满数据自然就错了。这不是算法问题而是对 Node 异步模型不熟悉。还有一个潜在风险是递归深度。JS 引擎的调用栈并不深如果数据构造得极端树退化成每条链只有一个子节点并且深度达到数万层递归版 DFS 直接报Maximum call stack size exceeded。笔试题一般不会卡这么狠但如果你在真实业务里处理组织架构树建议顺手改成显式栈的迭代写法const stack [target]; while (stack.length) { const node stack.pop(); const children tree.get(node) || []; for (const child of children) { if (visited.has(child)) continue; visited.add(child); result.push(child); stack.push(child); } }迭代版和递归版最终得到的节点集合完全一样只是访问顺序可能不同但因为我们最后会统一排序所以输出不受影响。这个“排序兜底”的特性帮了大忙也提醒我们只要结果最后要排序DFS 还是 BFS 都无所谓优先选择不爆栈的写法。4. Python 实现用最少代码完成同样的树遍历4.1 Python 完整实现与空输出处理Python 版本最简洁但简洁背后藏着一些其他语言不会直接告诉你的限制。先看完整代码import sys from collections import defaultdict def main(): lines sys.stdin.read().splitlines() if not lines: return n int(lines[0].strip()) tree defaultdict(list) for line in lines[1:n 1]: parent, child line.strip().split() tree[parent].append(child) target lines[n 1].strip() visited set() result [] def dfs(node): for child in tree.get(node, []): if child in visited: continue visited.add(child) result.append(child) dfs(child) dfs(target) result.sort() for node in result: print(node) if __name__ __main__: main()这里我特意用for node in result: print(node)而不是print(\n.join(result))原因是当 result 为空时\n.join(result)得到空字符串print()会多打一个换行。绝大多数判题系统对末尾空行不敏感但既然题面明确说“什么都不输出”那就做到最严谨。用 for 循环逐个打印空列表时一行都不会输出。4.2 defaultdict 和 get 的分工别把两件事混着写from collections import defaultdict之后tree[parent].append(child)不需要先判断 parent 是否在字典里这是 Python 最省心的地方。但注意defaultdict只有用[]访问时才触发默认值的创建get()方法是不会的。所以我在 DFS 里写的是tree.get(node, [])而不是tree[node]。如果写tree[node]当 node 不在字典里时会自动创建一个空列表。这个行为对结果没有直接影响但在大数据量下会往字典里塞一堆无意义的空 key白白增加内存和后续遍历的负担。用get则只是读取不做写入。这个细节写代码时顺带注意一下能让你的代码更干净。4.3 Python 递归深度最容易被忽略的限制Python 的默认递归深度上限是 1000 层。当树退化成一条很长的链时递归版 DFS 会在 1000 层左右抛出RecursionError。很多同学本地测试的数据很温和一上判题系统就崩就是因为没有意识到 Python 和 Java、JS 在这个问题上同样敏感。两种解决办法。第一种是任务量可控时直接放宽限制import sys sys.setrecursionlimit(100000)但这不是万能钥匙因为 Python 的递归最终还是会受 C 调用栈限制设得太高可能导致进程崩溃。第二种更稳妥就是改成显式栈迭代思路和前面 JS 版本一样stack [target] while stack: node stack.pop() for child in tree.get(node, []): if child in visited: continue visited.add(child) result.append(child) stack.append(child)我个人写笔试代码的习惯是能递归就递归因为代码短、好调试但心里始终绷着一根弦一旦题目没有明确说“树的深度很小”我就主动改成迭代版把风险降到零。5. 三份代码横向对比与选择建议5.1 三份代码逐项对比表为了方便直观比较我把三个版本的关键维度列成一张表维度JavaJavaScriptPython建表容器HashMapString, List Mapdefaultdict(list)去重集合HashSetStringSetset排序方式Collections.sort自定义比较函数list.sort()输入方式Scanner / BufferedReaderreadline 事件sys.stdin.read递归风险无默认限制但大深度仍可能栈溢出栈深相对有限默认 1000 层限制典型代码行数约 45 行约 40 行约 25 行时间复杂度O(n m k log k)O(n m k log k)O(n m k log k)三份代码的时间复杂度完全一样说明核心算法是语言无关的。区别主要在容器 API 的语法和各自环境的输入输出模型上。5.2 机考上到底选哪门语言我经常被问这种题用哪门语言最好我的回答是选你肌肉记忆最熟的那门。判题系统只看最终代码对不对不看语言加分Java、JS、Python 都是主流支持语言不存在“用某语言就占便宜”的情况。如果非要给一个策略我的做法是平时练习时用三种语言各写一遍笔试现场直接用最熟的一种。用 Python 验证算法思路最省时间用 Java 写起来结构感最强用 JS 则能顺便锻炼自己处理异步输入的能力。但临场换语言是大忌因为你很可能在某个不熟悉的语法细节上卡住白白浪费时间。5.3 时间复杂度和空间复杂度为什么一模一样不管用哪种语言算法层面的操作都是建表时每条关系插入一次O(n)DFS 或 BFS 时每条边最多访问一次O(n m)最后对 k 个结果排序O(k log k)。空间上都是邻接表 O(n) 加 visited O(m) 加结果 O(k)。语言不会改变复杂度只会改变常数因子。理解这一点很重要。面试官如果追问你能解释清楚“为什么三份代码复杂度和思路完全一致”就能证明你是真的理解算法本质而不是只会背代码。6. 从笔试走向业务树状查询在真实项目里的变体与坑6.1 菜单权限与组织架构里的同款问题这道笔试题绝不是只在刷题平台才有意义。后台管理系统的菜单树、企业组织架构、商品分类、地区级联本质都是同一种模型一张带parent_id的自引用表需要从某个节点出发查出它辖下的所有子节点。比如查某个部门下所有子部门用于权限分配查某个商品分类下所有叶子分类用于筛选条件。业务里数据量通常比笔试题大得多所以更强调缓存和批量查询。一般做法是先把整张表加载到内存按parent_id建索引再用同样的 DFS 思路生成树或者拉平子孙集合。这个过程和笔试代码几乎没有区别只是输入从命令行变成了数据库查询结果。6.2 真实业务里我会增强的三个点第一高频查询一定要加缓存。如果同一个 target 会被反复查询而树结构很少变化我会把“target - 子孙集合”的结果缓存起来。树结构一旦更新把相关缓存失效即可。这和算法题里“一次查询”的场景不同是工程化的必然要求。第二防环逻辑不能只放在当前查询里。业务脏数据可能让两个节点互相指向对方我在构建全局访问集合时会直接拒绝重复处理而不是“每次查询重新判断”。因为树结构本身是静态的环的存在会污染所有下游查询提前在数据装载阶段做一次环检测比查询时发现死循环再处理要划算得多。第三排序规则要跟着业务走。笔试要求字典序业务可不一定。菜单一般按 sortNo 排序组织架构可能按 level 和 order 排序商品分类可能要按拼音首字母排序。只要把排序函数抽出来单独写前面的 DFS/BFS 逻辑完全不用动。6.3 线上排查经验一个“少查一个节点”的 bug分享一个我真实处理过的线上问题。当时权限树查询结果总比预期少一个节点排查了很久最后发现数据里有条记录的parent_id指向了自己。也就是说某节点的父节点是它本身。DFS 代码在进入节点时先执行visited.add(node)然后遍历它的父节点时发现父节点已经被访问过就直接跳过了导致这个节点连同它真实的孩子节点都没有被正常收集。这个案例给我们的教训是visited 集合到底在哪个环节初始化、哪些节点要预先加入必须和“查询节点本身是否算子孙”这个问题一起想清楚。笔试里我们不用预先加入 target但业务代码里如果你沿用的是“先标记再遍历”的逻辑遇到自引用数据就会出问题。最稳妥的做法是在遍历子节点时才做 visited 判断和标记不要把入口节点无条件放进 visited。我前前后后用三种语言把这道题写了不下五遍每次重写都有新发现印象最深的是 JS 排序、Python 递归深度和 Java 输入换行这三个坑。我的建议是别只抄答案把它当模板反复练先闭着眼写出邻接表加 DFS再故意构造重复边、循环边、深层链表这些极端数据去测你的代码测完你就明白为什么 visited 和迭代栈是必需品了。把这道题吃透后面遇到组织架构树查询、菜单树过滤都是同一套打法。