从递归到极致优化：树结构构建的性能演进

从递归到极致优化：树结构构建的性能演进之路

一次简单的代码优化，性能提升 超千倍！本文通过实测数据，显现树结构构建中隐蔽的性能陷阱，并给出最佳实践。

📖 前言

在一样平常开发中，我们经常必要处置惩罚树形结构的数据：构造架构、菜单导航、商品分类、文件目次……这些场景都必要将扁平的数据库记载转换为层级树结构。
本日，让我们从最直观的递归实现开始，一步步优化到极致性能，看看这条优化之路上都有哪些坑。
本文将复兴：

• ✅ 构创建的常见方式有哪些？
  
• ✅ 为什么有些实如今大数据量下会瓦解？
  
• ✅ 怎样用一行代码实现数百倍性能提升？
  
• ✅ ILookup 为什么这么快？
  

测试情况：

• .NET 8.0
  
• 测试数据：10,000 ~ 100,000 个节点
  
• 硬件：平凡条记本电脑。11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz (2.42 GHz) | 16.0 GB
  

第一章：最直观的实现 - 递归方式

1.1 数据模子

起首界说我们的节点结构：

1. // 扁平数据（数据库记录）
2. public class Node
3. {
4.     public int Id { get; set; }
5.     public int ParentId { get; set; }  // 0 表示根节点
6.     public string Name { get; set; }
7. }
9. // 树结构
10. public class TreeItem<T>
11. {
12.     public T Node { get; set; }
13.     public List<TreeItem<T>> Children { get; set; } = new();
14. }

复制代码

1.2 递归实现

最直观的思绪：对每个节点，递归查找它的子节点。

1. public static TreeItem<Node> BuildTreeRecursive(List<Node> nodes)
2. {
3.     var root = nodes.First(n => n.ParentId == 0);
4.     return BuildNode(nodes, root);
5. }
7. private static TreeItem<Node> BuildNode(List<Node> allNodes, Node current)
8. {
9.     var item = new TreeItem<Node> { Node = current };
10.    
11.     // 🔴 关键：查找当前节点的所有子节点
12.     var children = allNodes.Where(n => n.ParentId == current.Id).ToList();
13.    
14.     foreach (var child in children)
15.     {
16.         item.Children.Add(BuildNode(allNodes, child));
17.     }
18.    
19.     return item;
20. }

复制代码

长处：

• ✅ 代码轻便、易明白
  
• ✅ 符合树的天然界说
  
• ✅ 得当小规模数据（< 1,000 节点）
  

缺点：

• ❌ 性能题目：时间复杂度 O(n²)
  
• ❌ 栈溢出风险：深度 > 1,000 层会瓦解
  

让我们先聊聊第二个题目。
第二章：递归的陷阱 - 栈溢出

2.1 题目重现

测试一个链表型树（每个节点只有一个子节点，深度 = 节点数）：

1. // 生成 10,000 个节点的链表树
2. var nodes = new List<Node>();
3. for (int i = 1; i <= 10000; i++)
4. {
5.     nodes.Add(new Node
6.     {
7.         Id = i,
8.         ParentId = i - 1,  // 形成链表：0 → 1 → 2 → ... → 10000
9.         Name = $"Node_{i}"
10.     });
11. }
13. var tree = BuildTreeRecursive(nodes);  // 💥 StackOverflowException!

复制代码

如许至少能提前发现题目，而不是让步伐直接瓦解。
第三章：迭代方式 - DFS 与 BFS

既然递归有深度限定，我们用迭代更换递归。
3.1 DFS（深度优先搜刮）- 使用栈

1. System.StackOverflowException: Exception of type 'System.StackOverflowException' was thrown.

复制代码

3.2 BFS（广度优先搜刮）- 使用队列

1. private const int MAX_DEPTH = 1000;
3. private static TreeItem<Node> BuildNode(List<Node> allNodes, Node current, int depth)
4. {
5.     if (depth > MAX_DEPTH)
6.         throw new InvalidOperationException("树深度超过限制，建议使用迭代方式");
7.    
8.     var item = new TreeItem<Node> { Node = current };
9.     var children = allNodes.Where(n => n.ParentId == current.Id).ToList();
10.    
11.     foreach (var child in children)
12.     {
13.         item.Children.Add(BuildNode(allNodes, child, depth + 1));
14.     }
15.    
16.     return item;
17. }

复制代码

3.3 迭代 vs 递归

特性递归DFS/BFS 迭代深度限定❌ ~1000层✅ 无穷定代码复杂度✅ 轻便⚠️ 稍复杂调试难度⚠️ 较难✅ 容易性能稍慢（函数调用开销）稍快看起来题目办理了？并没有！ 让我们做个性能测试。
第四章：性能灾难 - O(n²) 的原形

4.1 性能测试

为了贴合现实情况，我分了三个场景来举行测试：深层树(层级很深，每层节点数目少)，超宽树(层级很浅，但是每层节点数目多)，均衡树(深度和宽度都相对匀称，团体结构有点类似均衡二叉树)。节点数目：10万个(节点少了也看不出什么效果)。
直接贴图看效果（基于RELEASE模式编译）：

核心算法代码上面已经贴出，详细数据构建以及测试代码，这里就不贴出来了，如果有想看的朋侪，可以留言。

🚨 注意：

• 10 万节点用了 40-50秒！
  
• 递归方式早已栈溢出
  

4.2 性能分析：为什么这么慢？

让我们看看这段代码：

1. public static TreeItem<Node> BuildTreeDFS(List<Node> nodes)
2. {
3.     var root = new TreeItem<Node>
4.     {
5.         Node = nodes.First(n => n.ParentId == 0)
6.     };
7.    
8.     var stack = new Stack<TreeItem<Node>>();
9.     stack.Push(root);
11.     while (stack.Count > 0)
12.     {
13.         var current = stack.Pop();
14.         
15.         // 🔴 仍然是线性查找
16.         var children = nodes
17.             .Where(n => n.ParentId == current.Node.Id)
18.             .OrderByDescending(n => n.Id)
19.             .ToList();
20.         
21.         foreach (var child in children)
22.         {
23.             var childItem = new TreeItem<Node> { Node = child };
24.             current.Children.Add(childItem);
25.             stack.Push(childItem);
26.         }
27.     }
29.     return root;
30. }

复制代码

时间复杂度分析：

• 外层循环：O(n) - 遍历全部节点
  
• 内层 Where：O(n) - 每次扫描整个列表
  
• 总复杂度：O(n²)
  

详细盘算：

• 50,000 个节点 → 必要 25 亿次比力操纵！
  
• 100,000 个节点 → 必要 100 亿次比力操纵！
  

这就是性能杀手！
4.3 核心题目

1. public static TreeItem<Node> BuildTreeBFS(List<Node> nodes)
2. {
3.     var root = new TreeItem<Node>
4.     {
5.         Node = nodes.First(n => n.ParentId == 0)
6.     };
7.    
8.     var queue = new Queue<TreeItem<Node>>();
9.     queue.Enqueue(root);
11.     while (queue.Count > 0)
12.     {
13.         var current = queue.Dequeue();
14.         
15.         // 🔴 仍然是线性查找
16.         var children = nodes
17.             .Where(n => n.ParentId == current.Node.Id)
18.             .OrderBy(n => n.Id)
19.             .ToList();
20.         
21.         foreach (var child in children)
22.         {
23.             var childItem = new TreeItem<Node> { Node = child };
24.             current.Children.Add(childItem);
25.             queue.Enqueue(childItem);
26.         }
27.     }
29.     return root;
30. }

复制代码

这是现实项目中最常见的性能陷阱！
第五章：极致优化 - ILookup 的邪术

5.1 核心思绪：空间换时间

既然每次都要查找 ParentId == xxx 的节点，为什么不提前创建索引？

1. while (stack.Count > 0)  // 遍历所有节点：n 次
2. {
3.     var current = stack.Pop();
4.    
5.     // 每次都要扫描整个列表！
6.     var children = nodes.Where(n => n.ParentId == current.Node.Id);  // O(n)
7.     // ...
8. }

复制代码

5.2 什么是 ILookup？

ILookup 是 LINQ 提供的一个接口，类似于 Dictionary，但：

• 一键多值：主动处置惩罚一对多关系
  
• 不会抛非常：查询不存在的键返回空聚集
  
• 基于哈希表：查找时间 O(1)
  
• 只读不可变：线程安全
  

语法：

1. // 🔴 问题代码：在循环中使用 Where
2. foreach (var node in nodes)  // n 次
3. {
4.     var children = allNodes.Where(n => n.ParentId == node.Id);  // 每次 O(n)
5.     // 总复杂度：O(n²)
6. }

复制代码

5.3 优化后的代码

只需改一行！

1. // 🔴 原来：每次查找都要扫描整个列表
2. var children = nodes.Where(n => n.ParentId == parentId);  // O(n)
4. // ✅ 现在：提前建立索引，查找变成 O(1)
5. var lookup = nodes.ToLookup(n => n.ParentId);  // 一次性建立索引 O(n)
6. var children = lookup[parentId];  // 直接查找 O(1)

复制代码

改动对比：

1. // 创建
2. ILookup<int, Node> lookup = nodes.ToLookup(n => n.ParentId);
4. // 查询（即使 999 不存在也不会异常）
5. IEnumerable<Node> children = lookup[999];  // 返回空集合
7. // 检查是否存在
8. bool exists = lookup.Contains(999);
10. // 遍历所有分组
11. foreach (var group in lookup)
12. {
13.     Console.WriteLine($"ParentId: {group.Key}, Count: {group.Count()}");
14. }

复制代码

就这么简单！
第六章：性能对决 - 实测数据

6.1 完备测试

测试代码：

1. public static TreeItem<Node> BuildTreeDFSOptimized(IEnumerable<Node> nodes)
2. {
3.     var nodeList = nodes.ToList();
4.    
5.     // ✅ 核心优化：提前建立索引
6.     var lookup = nodeList.ToLookup(n => n.ParentId);  // 👈 只加了这一行！
7.    
8.     var root = new TreeItem<Node>
9.     {
10.         Node = nodeList.First(n => n.ParentId == 0)
11.     };
12.    
13.     var stack = new Stack<TreeItem<Node>>();
14.     stack.Push(root);
16.     while (stack.Count > 0)
17.     {
18.         var current = stack.Pop();
19.         
20.         // ✅ 从 O(n) 变成 O(1)
21.         var children = lookup[current.Node.Id]  // 👈 改这里
22.             .OrderByDescending(n => n.Id)
23.             .ToList();
24.         
25.         foreach (var child in children)
26.         {
27.             var childItem = new TreeItem<Node> { Node = child };
28.             current.Children.Add(childItem);
29.             stack.Push(childItem);
30.         }
31.     }
33.     return root;
34. }

复制代码

6.2 测试效果

6.3 性能分析

时间复杂度对比：
实现方式建索引查找子节点总复杂度原始方式-O(n)O(n²)优化方式O(n) 一次性O(1)O(n)内存占用：

• 原始方式：O(n) - 只存储节点
  
• 优化方式：O(n) - 节点 + Lookup 索引（额外约 20-30%）
  

1. public static TreeItem<Node> BuildTreeDFS(List<Node> nodes)
2. {
3. +   var lookup = nodes.ToLookup(n => n.ParentId);
4.     // ...
5.     while (stack.Count > 0)
6.     {
7.         var current = stack.Pop();
8. -       var children = nodes.Where(n => n.ParentId == current.Node.Id);
9. +       var children = lookup[current.Node.Id];
10.     }
11. }

复制代码

结论：

• ✅ 用 20-30% 内存调换 凌驾千倍的性能提升
  
• ✅ 绝对值得！
  

第七章：深入明白 ILookup

7.1 为什么 ILookup 这么快？

内部实现原理（简化版）：

1. internal class TreeBuilder
2. {
3.     private const int MAX_RECURSION_DEPTH = 1000; // 最大递归深度限制
5.     #region 1. 递归方式构建树（原始 - 每次线性查找，带深度保护）
6.     public static TreeItem<Node> BuildTreeRecursive(IEnumerable<Node> nodes)
7.     {
8.         var nodeList = nodes.ToList();
9.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
10.         
11.         return BuildRecursiveNode(nodeList, rootNode, 0);
12.     }
14.     private static TreeItem<Node> BuildRecursiveNode(List<Node> allNodes, Node currentNode, int depth)
15.     {
16.         // 深度保护：超过限制时抛出异常，避免真正的栈溢出
17.         if (depth > MAX_RECURSION_DEPTH)
18.         {
19.             throw new StackOverflowException($"递归深度超过限制 ({MAX_RECURSION_DEPTH})");
20.         }
22.         var treeItem = new TreeItem<Node> { Node = currentNode };
23.         
24.         // O(n) 线性查找子节点
25.         var children = allNodes.Where(n => n.ParentId == currentNode.Id).ToList();
26.         
27.         foreach (var child in children)
28.         {
29.             treeItem.Children.Add(BuildRecursiveNode(allNodes, child, depth + 1));
30.         }
31.         
32.         return treeItem;
33.     }
34.     #endregion
36.     #region 2. DFS方式构建树（原始 - 使用栈，每次线性查找）
37.     public static TreeItem<Node> BuildTreeDFS(IEnumerable<Node> nodes)
38.     {
39.         var nodeList = nodes.ToList();
40.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
41.         
42.         var root = new TreeItem<Node> { Node = rootNode };
43.         var stack = new Stack<TreeItem<Node>>();
44.         stack.Push(root);
46.         while (stack.Count > 0)
47.         {
48.             var current = stack.Pop();
49.             
50.             // O(n) 线性查找子节点
51.             var children = nodeList.Where(n => n.ParentId == current.Node.Id).OrderByDescending(n => n.Id).ToList();
52.             
53.             foreach (var child in children)
54.             {
55.                 var childItem = new TreeItem<Node> { Node = child };
56.                 current.Children.Add(childItem);
57.                 stack.Push(childItem);
58.             }
59.         }
61.         return root;
62.     }
63.     #endregion
65.     #region 3. BFS方式构建树（原始 - 使用队列，每次线性查找）
66.     public static TreeItem<Node> BuildTreeBFS(IEnumerable<Node> nodes)
67.     {
68.         var nodeList = nodes.ToList();
69.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
70.         
71.         var root = new TreeItem<Node> { Node = rootNode };
72.         var queue = new Queue<TreeItem<Node>>();
73.         queue.Enqueue(root);
75.         while (queue.Count > 0)
76.         {
77.             var current = queue.Dequeue();
78.             
79.             // O(n) 线性查找子节点
80.             var children = nodeList.Where(n => n.ParentId == current.Node.Id).OrderBy(n => n.Id).ToList();
81.             
82.             foreach (var child in children)
83.             {
84.                 var childItem = new TreeItem<Node> { Node = child };
85.                 current.Children.Add(childItem);
86.                 queue.Enqueue(childItem);
87.             }
88.         }
90.         return root;
91.     }
92.     #endregion
94.     #region 4. 优化的递归方式（使用字典索引 - O(n)，带深度保护）
95.     public static TreeItem<Node> BuildTreeRecursiveOptimized(IEnumerable<Node> nodes)
96.     {
97.         var nodeList = nodes.ToList();
98.         var lookup = nodeList.ToLookup(n => n.ParentId);
99.         
100.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
101.         
102.         return BuildRecursiveOptimizedNode(lookup, rootNode, 0);
103.     }
105.     private static TreeItem<Node> BuildRecursiveOptimizedNode(ILookup<int, Node> lookup, Node currentNode, int depth)
106.     {
107.         // 深度保护
108.         if (depth > MAX_RECURSION_DEPTH)
109.         {
110.             throw new StackOverflowException($"递归深度超过限制 ({MAX_RECURSION_DEPTH})");
111.         }
113.         var treeItem = new TreeItem<Node> { Node = currentNode };
114.         
115.         // O(1) 通过索引查找子节点
116.         var children = lookup[currentNode.Id];
117.         
118.         foreach (var child in children)
119.         {
120.             treeItem.Children.Add(BuildRecursiveOptimizedNode(lookup, child, depth + 1));
121.         }
122.         
123.         return treeItem;
124.     }
125.     #endregion
127.     #region 5. 优化的DFS（使用字典索引 - O(n)）
128.     public static TreeItem<Node> BuildTreeDFSOptimized(IEnumerable<Node> nodes)
129.     {
130.         var nodeList = nodes.ToList();
131.         var lookup = nodeList.ToLookup(n => n.ParentId);
132.         
133.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
134.         
135.         var root = new TreeItem<Node> { Node = rootNode };
136.         var stack = new Stack<TreeItem<Node>>();
137.         stack.Push(root);
139.         while (stack.Count > 0)
140.         {
141.             var current = stack.Pop();
142.             
143.             // O(1) 通过索引查找子节点
144.             var children = lookup[current.Node.Id].OrderByDescending(n => n.Id).ToList();
145.             
146.             foreach (var child in children)
147.             {
148.                 var childItem = new TreeItem<Node> { Node = child };
149.                 current.Children.Add(childItem);
150.                 stack.Push(childItem);
151.             }
152.         }
154.         return root;
155.     }
156.     #endregion
158.     #region 6. 优化的BFS（使用字典索引 - O(n)）
159.     public static TreeItem<Node> BuildTreeBFSOptimized(IEnumerable<Node> nodes)
160.     {
161.         var nodeList = nodes.ToList();
162.         var lookup = nodeList.ToLookup(n => n.ParentId);
163.         
164.         var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
165.         
166.         var root = new TreeItem<Node> { Node = rootNode };
167.         var queue = new Queue<TreeItem<Node>>();
168.         queue.Enqueue(root);
170.         while (queue.Count > 0)
171.         {
172.             var current = queue.Dequeue();
173.             
174.             // O(1) 通过索引查找子节点
175.             var children = lookup[current.Node.Id].OrderBy(n => n.Id).ToList();
176.             
177.             foreach (var child in children)
178.             {
179.                 var childItem = new TreeItem<Node> { Node = child };
180.                 current.Children.Add(childItem);
181.                 queue.Enqueue(childItem);
182.             }
183.         }
185.         return root;
186.     }
187.     #endregion        
188. }

复制代码

关键点：

• 使用 Dictionary 作为底层存储（哈希表）
  
• 查找时间：O(1) - 直接通过哈希值定位
  
• 不存在的键返回空聚集，不抛非常
  

7.2 ILookup vs Dictionary vs GroupBy

1. 为什么集中算法的最终内存都是一样的？
2. 1.✅ 输入数据相同：所有算法都使用同一个 nodes 列表（100,000 个 Node）
3. 2.✅ 输出结构相同：所有算法都构建相同的树结构（TreeItem 对象）
4. 3.✅ 最终内存相同：树的总内存 = 节点数 × 每个 TreeItem 的大小
6. // 构建后的树内存
7. 100,000 个 TreeItem<Node> 对象
8.   ├─ 每个 TreeItem: ~80 字节
9.   │    ├─ Node 引用: 8 字节
10.   │    └─ Children List: 72 字节（包含数组、计数等）
11.   └─ 总计: ~7.8 MB

复制代码

对比表：
特性GroupByDictionaryILookup创建索引耽误实验手动构建✅ 一行代码一键多值✅❌ 需手动✅查找速率O(n) 每次分组O(1)✅ O(1)键不存在返回 null抛非常✅ 返回空聚集代码轻便性⚠️❌✅保举度暂时分组一对一映射✅ 父子关系第八章：实战应用

8.1 常见场景

场景1：订单-订单项

1. // ToLookup 内部大致做了这些事
2. public static ILookup<TKey, TElement> ToLookup<TKey, TElement>(
3.     this IEnumerable<TElement> source,
4.     Func<TElement, TKey> keySelector)
5. {
6.     // 1. 创建哈希表
7.     var groups = new Dictionary<TKey, List<TElement>>();
8.    
9.     // 2. 遍历一次，建立索引 - O(n)
10.     foreach (var item in source)
11.     {
12.         var key = keySelector(item);
13.         
14.         if (!groups.ContainsKey(key))
15.             groups[key] = new List<TElement>();
16.         
17.         groups[key].Add(item);
18.     }
19.    
20.     // 3. 返回只读的 Lookup
21.     return new Lookup<TKey, TElement>(groups);
22. }
24. // 查找时 - O(1)
25. public IEnumerable<TElement> this[TKey key]
26. {
27.     get
28.     {
29.         return groups.ContainsKey(key)
30.             ? groups[key]
31.             : Enumerable.Empty<TElement>();  // 不存在返回空集合
32.     }
33. }

复制代码

场景2：部门-员工

1. var nodes = GetNodes();
3. // 1. GroupBy - 每次查询都重新分组（慢！）
4. var groups = nodes.GroupBy(n => n.ParentId);
5. var children1 = groups.FirstOrDefault(g => g.Key == 100)?.ToList();  // O(n) 每次都分组
7. // 2. Dictionary - 需要手动处理一对多
8. var dict = new Dictionary<int, List<Node>>();
9. foreach (var node in nodes)
10. {
11.     if (!dict.ContainsKey(node.ParentId))
12.         dict[node.ParentId] = new List<Node>();
13.     dict[node.ParentId].Add(node);
14. }
15. var children2 = dict.ContainsKey(100) ? dict[100] : new List<Node>();  // O(1) 但需要判断
17. // 3. Lookup - 一行搞定，自动处理一对多（快！）
18. var lookup = nodes.ToLookup(n => n.ParentId);
19. var children3 = lookup[100];  // O(1) 且不需要判断

复制代码

场景3：分类-商品

1. // ❌ 慢
2. foreach (var order in orders)
3. {
4.     order.Items = orderItems.Where(oi => oi.OrderId == order.Id).ToList();  // O(n²)
5. }
7. // ✅ 快
8. var itemsLookup = orderItems.ToLookup(oi => oi.OrderId);
9. foreach (var order in orders)
10. {
11.     order.Items = itemsLookup[order.Id].ToList();  // O(n)
12. }

复制代码

8.2 辨认性能陷阱

搜刮你的代码库，找这些模式：

1. var empLookup = employees.ToLookup(e => e.DepartmentId);
2. foreach (var dept in departments)
3. {
4.     dept.Employees = empLookup[dept.Id].ToList();
5. }

复制代码

CodeReview 清单：

• 循环中是否有 Where 查询？
  
• 是否多次遍历同一个聚集？
  
• 数据量是否大概凌驾 1,000？
  
• 能否用 ToLookup 或 ToDictionary 优化？
  

第九章：完备对比 - 六种实现

9.1 全部实现方式

实现方式时间复杂度深度限定代码复杂度保举场景递归(原始)O(n²)❌ ~1000层⭐⭐⭐⭐⭐❌ 不保举递归(优化)O(n)❌ ~1000层⭐⭐⭐⭐⭐小规模( 1000 层会栈溢出</ol>10.2 最佳实践

1. var prodLookup = products.ToLookup(p => p.CategoryId);
2. foreach (var category in categories)
3. {
4.     category.Products = prodLookup[category.Id].ToList();
5. }

复制代码

10.3 何时使用 ILookup

[table]场景是否使用一对多关系（父子、分类等）✅ 猛烈保举数据量 > 1,000✅ 必须使用必要频仍查找✅ 猛烈保举暂时分组（只用一次）⚠️ 思量 GroupBy一对一映射⚠️ 思量 Dictionary10.4 影象口诀

循环里有 Where，性能就完蛋；
提前建 Lookup，速率飞上天！

📚 参考资料

• LINQ ToLookup 官方文档
  
• 算法时间复杂度分析
  
• C# 性能优化最佳实践
  
• 完备源代码 (GitHub Or Gitee)
  

一点题外话

DFS（Depth-First Search 深度优先搜刮） 和BFS（Breadth-First Search 广度优先搜刮），这两个术语都来自图论，核心是搜刮（在数据结构中探求特定节点或路径）。
但我们在构创建时，只是按深度优先（大概广度优先）的次序访问节点并创建父子关系，并没有“搜刮”任何目标。严格来说，这应该叫深度优先遍历（Depth-First Traversal）或深度优先构建（Depth-First Construction），广度优先同理。
但为什么各人都风俗叫DFS/BFS？
这是范例的算法术语泛化征象：

• 劈头：图论中的DFS确实是为了搜刮/遍历
  
• 发展：人们发现“用栈处置惩罚树形结构”这种模式非常通用
  
• 泛化：任何使用栈来处置惩罚树/图结构的操纵，都被口语化地称为“用DFS的方式”
  
• 固化：口试、技能文章、开源代码都这么用，形成了约定俗成
  

类似例子另有许多：

• “用BFS爬取网页” → 实在只是广度优先遍历URL
  
• “递归遍历文件夹” → 并不是在搜刮什么
  
• “二叉树的前/中/后序遍历” → 实在也是DFS的特例，但很少人说“DFS二叉树”
  

为什么没人改正？
由于沟通资源高于正确性资源。当你口试时说“我用DFS把列表转成树”，全部人都秒懂。如果说“我用深度优先遍历的迭代方式，借助栈后进先出的特性来构建层级结构”——太啰嗦了，反而影响沟通服从。

但在现实开发中，“用DFS构创建”已经是行业黑话，各人都担当这个语义泛化后的寄义了。

🎯 结语

一次简单的代码优化，性能提升 凌驾千倍。
在现实项目中，如许的优化时机触目皆是。关键是：

• 丈量：用 Stopwatch 丈量，找到瓶颈
  
• 分析：辨认 O(n²) 的查找操纵
  
• 优化：用 ToLookup/ToDictionary 创建索引
  
• 验证：再次丈量，确认提升
  

记取：

过早优化是万恶之源，但该优化时别手软！

免责声明：如果侵犯了您的权益，请联系站长及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金.