做过的最复杂的组件

面试题：你做过的最复杂的组件是什么？

使用简单口语来回答，因为简单口语容易记忆，同时要显示出这个组件最复杂、我解决这个最复杂的组件是很不容易的。

“What is the most complex component you’ve built?”

English (natural spoken answer)

The most complex component I’ve worked on is a large-scale Virtualized Tree component, something like a file explorer used in a dashboard system.

At first glance, it looks simple, but it actually combines several hard problems together.

The main challenges were:

First, it’s a tree structure, not a flat list. So we need to handle nested nodes, expand and collapse states, and maintain hierarchy.

Second, we also need virtual scrolling, because the tree can contain tens of thousands of nodes. So rendering everything would completely break performance.

The hardest part was how to combine these two things efficiently.

What I did was redesign the data model. Instead of rendering the tree directly, I flattened it into a visible linear list, where each node carries its depth information.

Then I treated it like a normal virtual list, and only rendered the visible window based on scroll position.

On top of that, I optimized expand and collapse operations so they only update a small part of the visible list instead of recomputing the entire tree.

This reduced unnecessary re-rendering significantly and made the interaction very smooth even with large datasets.

Honestly, it wasn’t a trivial component. It forced me to think deeply about data structure design, performance trade-offs, and rendering strategy, not just React implementation.

中文

是的，我做过最复杂的组件，是一个大规模虚拟化 Tree 组件，类似文件管理器的左侧目录结构。

一开始看起来不复杂，但实际上它同时包含几个难点：

第一，它是一个树结构，不是普通 list，需要处理层级关系、展开/收起状态。

第二，它还要支持虚拟滚动，因为节点数量可能非常大，如果全部渲染会直接卡死。

最难的地方在于：如何把 Tree 和 Virtual List 合在一起。

我当时的做法是重新设计数据结构，不直接渲染 Tree，而是把它转换成一个带层级信息的线性数组（visible list）。

然后用普通虚拟列表的方式，只渲染当前可见区域。

同时在 expand / collapse 时，我没有重新遍历整棵树，而是只对受影响的子树做局部更新，从而避免了 O(N) 的全量计算。

这个优化让大数据量下的交互非常流畅。

说实话，这个组件不只是 UI 问题，而是一个涉及数据结构设计 + 性能优化 + 渲染模型设计的综合问题。

large list 的 virtualize我会做，但如果是large tree的 virtualize呢？可以做吗？我个人感觉就是不好确定是哪一些 nodes 显示出来，是这样吗？

你的直觉是对的，但真正的难点不是 Virtualization 本身，而是：

Tree 不是连续的数据，而 Virtual List 要求是连续的数据。

所以 Tree Virtualization = Tree Flattening + List Virtualization。

先看看为什么 List 很简单

假设一个 list


xxxxxxxxxx
0
1
2
3
4
5
6
7
8
...
99999

Virtual List 很容易。因为


xxxxxxxxxx
scrollTop = 800px
startIndex = Math.floor(scrollTop / itemHeight)
endIndex = startIndex + visibleCount

例如


xxxxxxxxxx
显示
40
41
42
43
44
45

index 是天然存在的。

Tree 为什么难？

Tree 是这种结构：


xxxxxxxxxx
A
 ├── A1
 │    ├── A11
 │    └── A12
 ├── A2
 │    ├── A21
 │    └── A22
 └── A3
B
 ├── B1
 └── B2

问题来了：假设


xxxxxxxxxx
A 是展开
A1 是展开
A2 是收起
B 是收起

真正应该显示的是


xxxxxxxxxx
A
A1
A11
A12
A2
A3
B

而不是


xxxxxxxxxx
A21
A22
B1
B2

因为它们不可见。所以：Virtual Scroll 根本不知道第 50 个 node 是谁。

真正的第一步：Flatten

几乎所有 Tree Virtualization 都会先做


xxxxxxxxxx
Tree
↓
Flatten
↓
Visible List

例如：Tree


xxxxxxxxxx
A
 ├── A1
 │    ├── A11
 │    └── A12
 ├── A2
 └── A3
B

变成


xxxxxxxxxx
[
 A,
 A1,
 A11,
 A12,
 A2,
 A3,
 B
]

注意：这里只放 visible node。

Flatten 怎么写？

DFS （depth-First Search 深度优先搜索）即可。例如


xxxxxxxxxx
function flatten(nodes, expandedSet) {
  const result = []
  function dfs(node, depth) {
    result.push({
      ...node,
      depth,
    })
    if (expandedSet.has(node.id)) {
      node.children?.forEach(child =>
        dfs(child, depth + 1)
      )
    }
  }
  nodes.forEach(node => dfs(node, 0))
  return result
}

最后得到


xxxxxxxxxx
[
 {id:'A', depth:0},
 {id:'A1', depth:1},
 {id:'A11', depth:2},
 {id:'A12', depth:2},
 {id:'A2', depth:1},
 {id:'A3', depth:1},
 {id:'B', depth:0},
]

这个数组就是 Virtual List 的数据源。

然后就和普通 Virtual List 一模一样

假设


xxxxxxxxxx
flatten.length = 20000

Virtual List 根本不知道这是 Tree。它只知道


xxxxxxxxxx
0
1
2
3
4
5

例如


xxxxxxxxxx
start = 150
end = 170

直接


xxxxxxxxxx
visible = flatten.slice(start, end)

就结束了。

Expand / Collapse 怎么办？

这是第二个难点。假设


xxxxxxxxxx
A
 ├── A1
 ├── A2
 └── A3

点击展开 A

以前


xxxxxxxxxx
flatten
A
B

展开后


xxxxxxxxxx
flatten
A
A1
A2
A3
B

其实就是：重新 flatten。

很多人以为要：


xxxxxxxxxx
insert
remove
shift index

实际上没必要。现代框架：


xxxxxxxxxx
expandedSet
↓
重新 DFS
↓
得到新的 flatten
↓
React diff

已经足够快。

真正的大数据怎么办？

假设


xxxxxxxxxx
100 万 node

每次 DFS？那就炸了。所以真正的大型 Tree（例如 IDE、文件管理器）不会每次重新 DFS 全树。

通常会维护：


xxxxxxxxxx
Tree
+
Visible List

例如


xxxxxxxxxx
visible
A
A1
A2
B

点击


xxxxxxxxxx
Expand A2

直接


xxxxxxxxxx
splice()
插进去
A21
A22
A23

而不是重新 DFS。

例如


xxxxxxxxxx
visible.splice(
  index + 1,
  0,
  ...children
)

Collapse

就是


xxxxxxxxxx
splice(
  index + 1,
  descendantCount
)

这样复杂度从


xxxxxxxxxx
O(N)

变成


xxxxxxxxxx
O(k)

其中


xxxxxxxxxx
k = 被展开的子树大小

最大的坑：Variable Height

真正困难的其实不是 Tree。而是：


xxxxxxxxxx
Tree
+
Virtual
+
Variable Height

例如


xxxxxxxxxx
Folder
  File
  File
  File
↓
Folder 展开以后高度变化

Virtual List 需要知道：


xxxxxxxxxx
第 1500 个 item 的 top 是多少？

如果高度不同：


xxxxxxxxxx
20
20
20
38
41
52
19

就不能再简单计算：


xxxxxxxxxx
index * itemHeight

需要维护：


xxxxxxxxxx
height cache
↓
prefix sum
↓
binary search

很多虚拟列表库（例如基于动态尺寸的实现）都会维护每个节点的测量高度和累计偏移，滚动定位时通过二分查找找到当前可见项。

面试官真正想听什么？

如果面试官问：

Tree 能不能做 Virtualization？

比较完整的回答可以是：

可以。核心思路不是直接虚拟化 Tree，而是先根据当前展开状态把 Tree 扁平化（Flatten）成一个只包含可见节点的线性数组，每个节点记录自己的 depth 用于缩进显示。然后 Virtual List 就可以像处理普通数组一样，根据滚动位置只渲染可见区间的节点。
如果数据规模不大，每次展开或收起时重新 DFS 生成扁平数组即可；如果节点数量非常大，为了避免每次都遍历整棵树，通常会维护一个可见节点列表，在展开时插入对应子树、收起时删除对应后代，将更新范围限制在受影响的子树，从而把更新成本降低到与子树大小相关，而不是与整棵树大小相关。
如果再结合动态高度（Variable Height），则还需要维护每个节点的高度缓存和累计偏移（或类似的数据结构），才能快速计算滚动位置与可见节点范围，这也是 Tree Virtualization 中最复杂的部分。

能使用双语简单口语，来说明一下怎么做吗？

English (Interview Answer)

Yes, it's definitely possible. The main challenge is that a tree is not a flat structure like a list.
For a normal virtualized list, every item already has an index, so it's easy to calculate which items should be rendered based on the scroll position.
A tree is different because some nodes are expanded while others are collapsed. That means not every node is actually visible.
So the first step is to flatten the tree into a visible list. I usually perform a DFS traversal and only include the nodes whose parents are expanded. During this process, I also record each node's depth so the UI knows how much indentation to apply.
After that, virtualization becomes exactly the same as a normal list. The virtual list only works with the flattened array and renders the visible range.
If the dataset isn't huge, I simply regenerate the flattened list whenever the user expands or collapses a node.
For very large trees, rebuilding the whole list every time can be expensive. In that case, I'd maintain the visible list incrementally, inserting or removing only the affected subtree when a node is expanded or collapsed.

中文（对应理解）

可以，完全可以。
最大的区别是，Tree 不是一个连续的 List。
普通 List 本来就有 index，所以很容易根据 scroll position 算出应该渲染哪些 item。
但是 Tree 有展开和收起的状态，所以很多节点其实并不会显示出来。
因此第一步通常会先把 Tree Flatten 成一个 Visible List。我一般会用 DFS，只把当前可见的节点放进数组，同时记录每个节点的 depth，用来控制缩进。
得到这个数组以后，Virtualization 就和普通 List 完全一样了，只需要根据 scroll position 渲染当前可见范围即可。
如果数据量不是特别大，每次展开或收起时重新生成这个数组就可以。
如果 Tree 非常大，我会维护一个可见节点列表，只更新受影响的那部分子树，而不是重新遍历整棵树。

更高级一点（面试加分）

如果面试官继续追问：

What if the tree contains millions of nodes?

你可以回答：

For extremely large trees, I wouldn't rebuild the flattened list every time. Instead, I'd keep a visible node list in memory. When a node is expanded, I'd insert only its visible descendants. When it's collapsed, I'd remove only that subtree. This reduces the update cost from the whole tree to just the affected subtree.

中文

如果节点特别多，比如几百万个，我不会每次都重新 Flatten 整棵树，而是维护一个可见节点列表。展开时只插入对应子树，收起时只删除对应子树，这样更新成本只和受影响的子树有关，而不是整个 Tree。

一句话总结（非常适合收尾）

Tree virtualization is basically "Tree Flattening + List Virtualization". Once the tree is flattened into a visible list, the virtualization logic is almost identical to a normal virtualized list.

中文：

Tree Virtualization 本质上就是：先把 Tree 扁平化成 Visible List，再使用普通的 List Virtualization。 这是很多成熟组件库（例如 IDE 文件树或大型文件管理器）采用的核心思路。

实现思路

核心思路

把 Tree 变成一个“带层级信息的线性数组”，然后当普通 List 做 Virtualization。

中文：

先“压平 Tree”，再用普通虚拟列表渲染。

Step 0：为什么 Tree 不能直接 virtualize？

Tree 是：


xxxxxxxxxx
src
 ├── components
 │    ├── Button
 │    └── Modal
 ├── pages
 │    ├── Home
 │    └── About
 └── package.json

问题：

👉 Virtual List 需要：


xxxxxxxxxx
index = 0..N

但 Tree：

有层级
有展开状态
顺序不是固定“平铺结构”

所以：

❌ 不能直接 virtualize Tree

Step 1：关键转折（v3 的核心思想）

我们不再直接用 Tree。我们先问一个问题：

“当前页面真正显示了哪些节点？”

例如：


xxxxxxxxxx
src (展开)
components (展开)
Button
Modal
pages (收起)
package.json

👉 UI 实际是：


xxxxxxxxxx
[src,
 components,
 Button,
 Modal,
 pages,
 package.json]

Step 2：核心突破 —— Flatten Tree

我们把 Tree 转换成：


xxxxxxxxxx
VisibleNode[] = Linear Array

每个节点带一个关键字段：


xxxxxxxxxx
depth: number

示例结果：


xxxxxxxxxx
src              depth 0
components       depth 1
Button           depth 2
Modal            depth 2
pages            depth 1
package.json     depth 0

Step 3：Flatten 怎么做？

核心就是 DFS，但有一个关键规则：

只遍历“展开的节点”


xxxxxxxxxx
if node is expanded → traverse children
else skip children

逻辑：


xxxxxxxxxx
visit node
  ↓
add to result
  ↓
if expanded → dfs(children)

Step 4：Flatten 的结果是什么？

它不是 Tree：


xxxxxxxxxx
❌ Tree structure

而是：


xxxxxxxxxx
✅ Linear visible array

Step 5：Virtualization 变得极其简单

现在：


xxxxxxxxxx
visibleNodes = flat array

我们直接：


xxxxxxxxxx
startIndex = scrollTop / rowHeight
endIndex = startIndex + visibleCount

然后：


xxxxxxxxxx
slice(startIndex, endIndex)

Step 6：v3 的整体结构


xxxxxxxxxx
Tree
  ↓
flattenTree(expandedSet)
  ↓
visibleNodes[]
  ↓
Virtual List
  ↓
render

Step 7：Expand / Collapse 怎么处理？

Expand：


xxxxxxxxxx
update expandedSet
re-run flattenTree

Collapse：


xxxxxxxxxx
update expandedSet
re-run flattenTree

注意：

❗ 每次变更都会重新 flatten

优缺点（面试重点）

👍 优点：

实现最简单
思路清晰
非常适合面试基础回答
性能对小/中型 Tree 足够

👎 缺点：

每次 expand/collapse 都 O(N)
大 Tree 会重复遍历
没有增量更新

代码实现

目录结构：


xxxxxxxxxx
src/
│
├── App.tsx
├── VirtualTree.tsx
├── flatten.ts
├── types.ts
└── data.ts

整个代码大约 180 行。

特点：

✅ React + TypeScript
✅ 不依赖任何 Virtual Library
✅ DFS Flatten
✅ Expand / Collapse
✅ 真正 Virtual Scroll
✅ 面试可以直接手写讲解

Step1：types.ts


xxxxxxxxxx
export interface TreeNode {
  id: string;
  name: string;
  children?: TreeNode[];
}
export interface VisibleNode extends TreeNode {
  depth: number;
}

Step2：data.ts


xxxxxxxxxx
import { TreeNode } from "./types";
export const treeData: TreeNode[] = [
  {
    id: "src",
    name: "src",
    children: [
      {
        id: "components",
        name: "components",
        children: [
          {
            id: "button",
            name: "Button.tsx",
          },
          {
            id: "modal",
            name: "Modal.tsx",
          },
        ],
      },
      {
        id: "pages",
        name: "pages",
        children: [
          {
            id: "home",
            name: "Home.tsx",
          },
          {
            id: "about",
            name: "About.tsx",
          },
        ],
      },
      {
        id: "package",
        name: "package.json",
      },
    ],
  },
];

Step3：flatten.ts

这是整个 Tree Virtualization 最重要的一步。


xxxxxxxxxx
import { TreeNode, VisibleNode } from "./types";
export function flattenTree(
  nodes: TreeNode[],
  expanded: Set<string>
): VisibleNode[] {
  const result: VisibleNode[] = [];
  function dfs(node: TreeNode, depth: number) {
    result.push({
      ...node,
      depth,
    });
    if (
      node.children &&
      expanded.has(node.id)
    ) {
      node.children.forEach((child) =>
        dfs(child, depth + 1)
      );
    }
  }
  nodes.forEach((node) => dfs(node, 0));
  return result;
}

Step4：VirtualTree.tsx

这个组件里面包含：


xxxxxxxxxx
flatten
↓
virtual
↓
render


xxxxxxxxxx
import { useMemo, useState } from "react";
import { TreeNode } from "./types";
import { flattenTree } from "./flatten";
const ROW_HEIGHT = 32;
const HEIGHT = 220;
interface Props {
  tree: TreeNode[];
}
export default function VirtualTree({
  tree,
}: Props) {
  const [expanded, setExpanded] = useState(
    new Set(["src"])
  );
  const [scrollTop, setScrollTop] =
    useState(0);
  const visibleNodes = useMemo(
    () => flattenTree(tree, expanded),
    [tree, expanded]
  );
  const totalHeight =
    visibleNodes.length * ROW_HEIGHT;
  const startIndex = Math.floor(
    scrollTop / ROW_HEIGHT
  );
  const visibleCount =
    Math.ceil(HEIGHT / ROW_HEIGHT);
  const endIndex =
    startIndex + visibleCount + 1;
  const items = visibleNodes.slice(
    startIndex,
    endIndex
  );
  function toggle(id: string) {
    const next = new Set(expanded);
    if (next.has(id)) {
      next.delete(id);
    } else {
      next.add(id);
    }
    setExpanded(next);
  }
  return (
    <div
      style={{
        height: HEIGHT,
        overflow: "auto",
        border: "1px solid #ddd",
      }}
      onScroll={(e) =>
        setScrollTop(
          e.currentTarget.scrollTop
        )
      }
    >
      <div
        style={{
          height: totalHeight,
          position: "relative",
        }}
      >
        {items.map((node, index) => {
          const realIndex =
            startIndex + index;
          return (
            <div
              key={node.id}
              onClick={() =>
                toggle(node.id)
              }
              style={{
                position: "absolute",
                top:
                  realIndex *
                  ROW_HEIGHT,
                height: ROW_HEIGHT,
                lineHeight:
                  `${ROW_HEIGHT}px`,
                left:
                  node.depth * 20,
                cursor: "pointer",
              }}
            >
              {node.children
                ? expanded.has(node.id)
                  ? "📂"
                  : "📁"
                : "📄"}{" "}
              {node.name}
            </div>
          );
        })}
      </div>
    </div>
  );
}

Step5：App.tsx


xxxxxxxxxx
import VirtualTree from "./VirtualTree";
import { treeData } from "./data";
export default function App() {
  return (
    <div
      style={{
        width: 400,
        margin: "40px auto",
      }}
    >
      <VirtualTree
        tree={treeData}
      />
    </div>
  );
}

运行效果

第一次：


xxxxxxxxxx
📂 src
    📁 components
    📁 pages
    📄 package.json

点击 components


xxxxxxxxxx
📂 src
    📂 components
        📄 Button.tsx
        📄 Modal.tsx
    📁 pages
    📄 package.json

点击 pages


xxxxxxxxxx
📂 src
    📂 components
        📄 Button.tsx
        📄 Modal.tsx
    📂 pages
        📄 Home.tsx
        📄 About.tsx
    📄 package.json

整个过程中，真正渲染的只有：


xxxxxxxxxx
const items = visibleNodes.slice(startIndex, endIndex);

这就是 Virtualization。

这只是第一版（Fixed Height）

真正生产环境的 Virtual Tree（例如 VS Code Explorer、Chrome DevTools、IDE 文件树）还会继续优化，例如：

Overscan（上下多渲染几行，避免滚动闪烁）
Variable Row Height（不同节点高度不同）
增量更新 Visible List（展开/收起时不重新 DFS 整棵树）
滚动位置保持（展开后避免视图突然跳动）
键盘导航（↑ ↓ ← →、Home、End）
ARIA 无障碍支持

这些才是真正接近 react-arborist、VS Code Explorer 等专业 Tree Virtualization 实现的核心技术。如果你准备高级前端或 Staff 级面试，我也可以带你把这个 Demo 一步步演进成接近生产级的实现。

继续优化

如果让我设计一套面试学习路线，我会按下面的版本逐步演进，每一步都对应一个真实工程问题。


xxxxxxxxxx
v1  Tree + Flatten + Fixed Virtual List        ⭐⭐（我们已经完成）
            ↓
v2  Overscan                                  ⭐⭐⭐
            ↓
v3  Variable Height                           ⭐⭐⭐⭐
            ↓
v4  Incremental Visible List                  ⭐⭐⭐⭐⭐
            ↓
v5  Async Load Children                       ⭐⭐⭐⭐⭐
            ↓
v6  Production Virtual Tree                   ⭐⭐⭐⭐⭐⭐

v2 Overscan（真实项目第一步）

现在我们的代码有一个问题。

假设：


xxxxxxxxxx
viewport
--------------------
Item 100
Item 101
Item 102
Item 103
--------------------

滚动 1px

以前：


xxxxxxxxxx
卸载100
挂载104

再滚


xxxxxxxxxx
卸载101
挂载105

React 一直在：


xxxxxxxxxx
mount
unmount
mount
unmount

所以滚动会有一点点抖。

真正 Virtual List 都会这样：


xxxxxxxxxx
viewport
--------------------
98
99
100
101
102
103
104
105
--------------------

也就是说：


xxxxxxxxxx
多渲染上下几行

这就是 Overscan。

代码改动非常小。

以前：


xxxxxxxxxx
const startIndex = Math.floor(scrollTop / ROW_HEIGHT)
const endIndex =
  startIndex + visibleCount + 1

改成：


xxxxxxxxxx
const overscan = 5
const startIndex = Math.max(
    0,
    Math.floor(scrollTop / ROW_HEIGHT) - overscan
)
const endIndex = Math.min(
    visibleNodes.length,
    startIndex + visibleCount + overscan * 2
)

是不是一下就流畅很多。

v3 真正的大坑：Variable Height

这是所有 Virtual List 最难的地方。

假设：


xxxxxxxxxx
Folder
File
File
README

现在：


xxxxxxxxxx
Folder 展开

Folder 变高了。

以前：


xxxxxxxxxx
32
32
32
32

现在：


xxxxxxxxxx
56
28
30
45

Virtual List 就不能再：


xxxxxxxxxx
top = index * height

因为：


xxxxxxxxxx
index=3
到底是多少？

必须：


xxxxxxxxxx
56
+
28
+
30
=
114

所以生产环境都会维护：


xxxxxxxxxx
heightMap
↓
prefixSum
↓
binarySearch

这是 TanStack Virtual 最大的一部分源码。

v4 真正的大型 Tree

这是 Google、VS Code 最喜欢问的。我们现在：

点击：


xxxxxxxxxx
展开 src

会：


xxxxxxxxxx
DFS
整个 Tree

哪怕：


xxxxxxxxxx
100 万节点

也重新 DFS。

复杂度：


xxxxxxxxxx
O(N)

这就是 Demo。

真正生产不会这样。

生产环境会维护：


xxxxxxxxxx
visibleNodes

例如：


xxxxxxxxxx
src
components
pages
package.json

点击：


xxxxxxxxxx
components

不会重新 DFS。

而是：


xxxxxxxxxx
找到 components

然后：


xxxxxxxxxx
splice()

变成：


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

是不是只改了一小段。

复杂度：


xxxxxxxxxx
O(k)

其中：


xxxxxxxxxx
k = 子树大小

不是：


xxxxxxxxxx
整个 Tree

v5 懒加载（Async Tree）

例如 GitHub：


xxxxxxxxxx
▶ node_modules

根本不知道：


xxxxxxxxxx
children

点击：


xxxxxxxxxx
展开

才：


xxxxxxxxxx
fetch()
↓
API
↓
children

所以 Tree 会变成：


xxxxxxxxxx
children
undefined

不是：


xxxxxxxxxx
[]

展开：


xxxxxxxxxx
Loading...

回来：


xxxxxxxxxx
children
有数据

重新插进去。

v6 真正生产版本

这时候你的组件其实已经接近：

VS Code Explorer
Chrome DevTools
Figma Layer Panel
Notion 左侧目录

架构会变成：


xxxxxxxxxx
Tree
↓
TreeStore
        │
        ├── expandedSet
        ├── visibleNodes
        ├── heightCache
        ├── nodeMap
        ├── parentMap
        └── childrenMap
↓
Virtual Engine
↓
Render

这里你会发现，Virtual List 已经不是重点了。

真正复杂的是：


xxxxxxxxxx
TreeStore

所有状态都在里面。

React Component：

几乎只是：


xxxxxxxxxx
TreeStore
↓
visibleNodes
↓
render()

如果我是面试官，我最希望你能写出来的是哪一版？

我不会让候选人写 TanStack Virtual 那种几千行源码。

我会希望看到下面这个演进过程：


xxxxxxxxxx
✅ v1 Flatten Tree
        ↓
✅ v2 Fixed Virtual List
        ↓
✅ v3 Overscan
        ↓
✅ v4 Incremental Update（⭐⭐⭐⭐⭐）

v4 是最有价值的。

因为它体现的是数据结构和算法能力，而不是会不会用虚拟列表库。

我建议我们下一步实现 v4

不要继续优化滚动，而是重构数据结构。

我们会把现在每次都执行：


xxxxxxxxxx
flattenTree(tree, expanded)

改造成维护一个长期存在的 visibleNodes 数组：


xxxxxxxxxx
visibleNodes
├── src
├── components
├── Button
├── Modal
├── pages
└── package.json

展开 components 时，我们只在数组中插入对应的子节点；收起时，只删除它的后代，而不再重新 DFS 整棵树。

这一版是真正生产级 Tree Virtualization 的核心，也是很多高级前端面试最希望听到的实现思路。

实现v4

太好了，我们开始做 v4：Incremental Visible List。

这一版开始，我们的思路会发生一个很大的变化。

不再每次都 flattenTree()，而是把 visibleNodes 当作真正的数据源来维护。

这也是 VS Code、Chrome DevTools、很多 Tree 组件的核心思想。

先看看 v1 的问题

我们之前的代码：


xxxxxxxxxx
const visibleNodes = useMemo(
  () => flattenTree(tree, expanded),
  [tree, expanded]
)

假设 Tree 是这样的：


xxxxxxxxxx
src
├── components
│   ├── Button
│   └── Modal
├── pages
│   ├── Home
│   └── About
└── package.json

第一次：


xxxxxxxxxx
visibleNodes
src
components
pages
package.json

点击：


xxxxxxxxxx
components

React：


xxxxxxxxxx
重新 DFS
↓
重新生成
visibleNodes

得到


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

如果 Tree 有：


xxxxxxxxxx
100 万 node

每点一次：


xxxxxxxxxx
DFS()
100 万

是不是很浪费？

真正生产环境

生产环境不会这样。

它会一直维护：


xxxxxxxxxx
const [visibleNodes, setVisibleNodes] = useState(...)

以后：只修改这个数组。

所以：


xxxxxxxxxx
Tree

变成：


xxxxxxxxxx
Tree
+
VisibleNodes

两个同时存在。

第一步：VisibleNode 要记录更多信息

以前：


xxxxxxxxxx
interface VisibleNode {
    id
    name
    depth
}

现在不够。因为：点击


xxxxxxxxxx
components

我要知道：


xxxxxxxxxx
children 是谁？

所以：


xxxxxxxxxx
export interface VisibleNode {
  id: string
  name: string
  depth: number
  children?: TreeNode[]
}

其实最简单就是：


xxxxxxxxxx
VisibleNode extends TreeNode

这个我们之前已经这么做了。

第二步：第一次还是 DFS

注意：第一次还是要 Flatten。

例如：


xxxxxxxxxx
src

展开。得到：


xxxxxxxxxx
src
components
pages
package.json

以后：再也不用 DFS 整棵 Tree。

第三步：Expand

这是最重要的。

假设现在：


xxxxxxxxxx
0 src
1 components
2 pages
3 package.json

点击：


xxxxxxxxxx
components

应该变成：


xxxxxxxxxx
0 src
1 components
2 Button
3 Modal
4 pages
5 package.json

注意：

Button

Modal

是插进去的。

不是重新生成。

所以找到：


xxxxxxxxxx
components

index：


xxxxxxxxxx
const index =
    visibleNodes.findIndex(...)

例如：


xxxxxxxxxx
index = 1

然后DFS：

但是：只 DFS components。

得到：


xxxxxxxxxx
Button
Modal

注意：不是 DFS 整棵 Tree。

只是：


xxxxxxxxxx
components.children

然后：


xxxxxxxxxx
visibleNodes.splice(
    index + 1,
    0,
    ...children
)

是不是完成了？

Collapse 怎么办？

现在：


xxxxxxxxxx
src
components
Button
Modal
pages
package.json

点击：


xxxxxxxxxx
components

应该删掉：


xxxxxxxxxx
Button
Modal

怎么删？

很多人第一反应：DFS。

其实不用。

因为数组已经是：


xxxxxxxxxx
components
Button
Modal
pages

注意：Button Modal 都有


xxxxxxxxxx
depth=2

而pages是：


xxxxxxxxxx
depth=1

所以一直删到：


xxxxxxxxxx
depth <= 当前 depth

停止。

例如：

当前：


xxxxxxxxxx
components
depth=1

后面：


xxxxxxxxxx
Button
depth=2

删。

继续：


xxxxxxxxxx
Modal
depth=2

删。

继续：


xxxxxxxxxx
pages
depth=1

停止。

是不是根本不用 DFS？

所以 Collapse 非常漂亮。

代码几乎就是：


xxxxxxxxxx
let end = index + 1;
while (
    end < visibleNodes.length &&
    visibleNodes[end].depth > current.depth
) {
    end++;
}
visibleNodes.splice(
    index + 1,
    end - index - 1
);

复杂度：


xxxxxxxxxx
O(k)

k：

就是：


xxxxxxxxxx
Button
Modal

两项。

不是：


xxxxxxxxxx
100 万

整个 Toggle 流程

以后 Expand：


xxxxxxxxxx
点击
↓
找到 index
↓
DFS 当前 children
↓
splice 插进去
↓
setVisibleNodes()

Collapse：


xxxxxxxxxx
点击
↓
找到 index
↓
找到所有 descendant
↓
splice 删除
↓
setVisibleNodes()

为什么 VS Code 能做到几百万文件不卡？

因为它维护的是：


xxxxxxxxxx
visibleNodes

而不是：


xxxxxxxxxx
tree
↓
DFS
↓
visibleNodes

每次重建。

所以：

展开一个文件夹：

真正变化的只有：


xxxxxxxxxx
20 个 children

不是：


xxxxxxxxxx
100 万 node

下一步（真正开始写代码）

这一节我们主要理解了算法。

下一节我建议直接重构我们的 VirtualTree.tsx，把：


xxxxxxxxxx
useMemo(() => flattenTree(...))

彻底删掉。

改成维护：


xxxxxxxxxx
const [visibleNodes, setVisibleNodes] = useState(...)

然后实现两个真正的生产级函数：


xxxxxxxxxx
expandNode(nodeId)
collapseNode(nodeId)

你会看到整个组件从“Demo 思路”升级为“生产级架构”，这也是很多成熟 Tree 组件内部采用的核心实现方式。

v4 代码实现

很好，这一步开始就是真正的工程实现了。

这一版我不会只给你几个函数，而是直接把 VirtualTree.tsx 改造成生产环境更接近的架构。

第一步：以前的数据流

我们以前是：


xxxxxxxxxx
Tree
      ↓
flattenTree()
      ↓
visibleNodes
      ↓
render

也就是说，每次点击都会重新：


xxxxxxxxxx
flattenTree(tree, expanded)

现在的数据流

改成：


xxxxxxxxxx
Tree（永远不变）
        │
        │（初始化一次）
        ▼
visibleNodes（State）
        │
        ├── expand()
        ├── collapse()
        ▼
render

以后：render 永远使用 visibleNodes。Tree 只是数据仓库（Source of Truth）。

第二步：State 改掉

以前：


xxxxxxxxxx
const [expanded, setExpanded] = useState(new Set(["src"]))
const visibleNodes = useMemo(
  () => flattenTree(tree, expanded),
  [tree, expanded]
)

现在改成：


xxxxxxxxxx
const [expanded, setExpanded] = useState(
  new Set(["src"])
)
const [visibleNodes, setVisibleNodes] =
  useState(() =>
    flattenTree(tree, new Set(["src"]))
  )

以后：

render 全部来自


xxxxxxxxxx
visibleNodes

而不是


xxxxxxxxxx
flattenTree(...)

第三步：Expand

我们写一个函数：


xxxxxxxxxx
function expandNode(id: string) {
}

第一件事：找到点击的是谁。


xxxxxxxxxx
const index = visibleNodes.findIndex(
  node => node.id === id
)
if (index === -1) return

例如：


xxxxxxxxxx
0 src
1 components
2 pages
3 package.json

点击：


xxxxxxxxxx
components

得到：


xxxxxxxxxx
index = 1

第四步：找到 children


xxxxxxxxxx
const current = visibleNodes[index]
if (!current.children?.length) {
    return
}

例如：


xxxxxxxxxx
components
↓
children

就是：


xxxxxxxxxx
Button
Modal

第五步：只 Flatten 当前子树

注意！

不是：


xxxxxxxxxx
flattenTree(tree)

而是：


xxxxxxxxxx
flattenTree(
    current.children,
    expanded
)

这里还有一个小细节。

因为 Button 应该：


xxxxxxxxxx
depth=2

所以以前：


xxxxxxxxxx
flattenTree()

固定：


xxxxxxxxxx
depth=0

现在需要改一下。

我们修改：


xxxxxxxxxx
flattenTree()

增加：


xxxxxxxxxx
baseDepth

例如：


xxxxxxxxxx
flattenTree(
    children,
    expanded,
    current.depth + 1
)

DFS 从：


xxxxxxxxxx
depth=2

开始。

所以 flatten.ts 变成：


xxxxxxxxxx
export function flattenTree(
  nodes,
  expanded,
  depth = 0
)

DFS：


xxxxxxxxxx
dfs(node, depth)

而不是：


x
dfs(node, 0)

是不是一下灵活很多？

第六步：插进去

得到：


xxxxxxxxxx
Button
Modal

直接：


xxxxxxxxxx
const next = [...visibleNodes]
next.splice(
    index + 1,
    0,
    ...children
)
setVisibleNodes(next)

是不是结束了？

整个过程：


xxxxxxxxxx
components
↓
Button
Modal
↓
splice()
↓
render

没有重新 DFS 整棵树。

Collapse

Collapse 更漂亮。

现在：


xxxxxxxxxx
0 src
1 components
2 Button
3 Modal
4 pages
5 package.json

点击：


xxxxxxxxxx
components

当前：


xxxxxxxxxx
depth=1

开始：


xxxxxxxxxx
let end = index + 1

循环：


xxxxxxxxxx
Button
depth=2

继续。


xxxxxxxxxx
Modal
depth=2

继续。


xxxxxxxxxx
pages
depth=1

停。

所以：


xxxxxxxxxx
const removeCount =
    end - index - 1

这里：


xxxxxxxxxx
removeCount=2

然后：


xxxxxxxxxx
next.splice(
    index + 1,
    removeCount
)

完成。

Toggle

最后：


xxxxxxxxxx
function toggle(node) {
    if(expanded.has(node.id)) {
        collapseNode(node.id)
    } else {
        expandNode(node.id)
    }
}

现在复杂度是多少？

假设：

整个 Tree：


xxxxxxxxxx
1000000 nodes

点击：


xxxxxxxxxx
components

里面：


xxxxxxxxxx
Button
Modal

以前：


xxxxxxxxxx
DFS()
1000000

现在：


xxxxxxxxxx
DFS()
2

因为只处理：


xxxxxxxxxx
children

是不是一下：


xxxxxxxxxx
O(N)
↓
O(k)

这里还有一个隐藏 Bug（也是很多面试官喜欢追问的）

来看下面这个 Tree：


xxxxxxxxxx
src
└── components
      ├── Button
      │      ├── index.ts
      │      └── styles.css
      └── Modal

假设：


xxxxxxxxxx
Button

已经展开。

也就是说：


xxxxxxxxxx
expanded
=
src
components
Button

现在：

第一次展开：


xxxxxxxxxx
components

应该出现：


xxxxxxxxxx
components
    Button
        index.ts
        styles.css
    Modal

而不是：


components
    Button
    Modal

为什么？

因为 Button 本来就在 expanded 集合里。

也就是说：

我们插入 components.children 时，不能只插入第一层，而要递归展开那些已经处于 expanded 状态的子节点。

这也是为什么我前面坚持保留 flattenTree(children, expanded, baseDepth) 的原因。

它不仅能生成第一层，还能自动把那些“已经展开”的子树一起展开。

下一节（真正生产级）

到这里，我们已经实现了：

✅ 增量更新 visibleNodes
✅ 不重新遍历整棵树
✅ 支持恢复已展开的子树

下一步我建议继续升级，实现 NodeMap + ParentMap。

这是 VS Code、IDE、文件管理器最常见的数据结构。引入它之后，findIndex、查找节点、懒加载、拖拽排序等操作都会变得更高效，也更符合生产级 Tree 组件的内部设计。

下一步

好，下面这一步开始，就真的进入生产级 Tree 组件了。

其实我们刚刚的版本还有一个问题。

为什么还不够？

现在我们的代码里，每次点击都会：


xxxxxxxxxx
const index = visibleNodes.findIndex(
    node => node.id === id
)

复杂度：


xxxxxxxxxx
O(N)

如果：


xxxxxxxxxx
visibleNodes
100000

每点击一次：


xxxxxxxxxx
findIndex()
100000

其实还是有点浪费。

真正生产环境

真正的 Tree 一般都会维护一个 Store。

例如：


xxxxxxxxxx
TreeStore
├── nodeMap
├── parentMap
├── childrenMap
├── visibleNodes
├── expandedSet
└── selectedSet

React Component 只是：


xxxxxxxxxx
TreeStore
↓
visibleNodes
↓
render

你会发现：React 根本不关心 Tree。Tree 全部在 Store 里面。

第一张 Map：nodeMap

为什么需要？

Tree：


xxxxxxxxxx
src
    components
        Button
        Modal

以前想找到：


xxxxxxxxxx
Button

需要 DFS 整棵 Tree。

生产不会。

初始化一次：


xxxxxxxxxx
const nodeMap = new Map()
nodeMap.set("src", src)
nodeMap.set("components", components)
nodeMap.set("button", button)
nodeMap.set("modal", modal)

以后：


xxxxxxxxxx
nodeMap.get("button")

直接：


xxxxxxxxxx
O(1)

是不是比 DFS 快很多。

第二张 Map：parentMap

为什么？

例如：


xxxxxxxxxx
Button

我要知道：


xxxxxxxxxx
父是谁？

以前 DFS。

现在：


xxxxxxxxxx
parentMap
button
↓
components

直接：


xxxxxxxxxx
parentMap.get("button")

得到：


xxxxxxxxxx
components

很多功能都会用。

例如：


xxxxxxxxxx
Breadcrumb
src
↓
components
↓
Button

第三张 Map：childrenMap

虽然 Node 已经有：


xxxxxxxxxx
children

为什么还维护？

因为很多 Tree 的 children 是：


xxxxxxxxxx
undefined

懒加载。或者 children 存在数据库。

真正生产一般：


xxxxxxxxxx
childrenMap
↓
parentId
↓
children[]

例如：


xxxxxxxxxx
childrenMap
src
↓
[
components,
pages,
package
]

以后 Expand 直接：


xxxxxxxxxx
childrenMap.get(id)

不用：


xxxxxxxxxx
node.children

初始化一次

整个 Tree 只 DFS 一次。


xxxxxxxxxx
function buildMaps(tree){
}

DFS：


xxxxxxxxxx
function dfs(node,parent){
    nodeMap.set(node.id,node)
    parentMap.set(
        node.id,
        parent?.id
    )
    childrenMap.set(
        node.id,
        node.children ?? []
    )
    node.children?.forEach(...)
}

以后 Tree 再也不用 DFS。

Expand

以前：


xxxxxxxxxx
const node =
visibleNodes[index]

现在直接：


xxxxxxxxxx
const node =
nodeMap.get(id)

是不是：


xxxxxxxxxx
O(1)

然后：


xxxxxxxxxx
const children =
childrenMap.get(id)

也是：


xxxxxxxxxx
O(1)

Collapse

Collapse 还是扫描：


xxxxxxxxxx
visibleNodes

为什么？

因为 Visible List 就是：


xxxxxxxxxx
DFS 顺序

例如：


xxxxxxxxxx
src
components
Button
Modal
pages

Button 后面一定还是 Modal 。不会跑到 src 前面。

所以扫描：


xxxxxxxxxx
depth

就是最快。

很多人会觉得是不是还能：


xxxxxxxxxx
O(1)

其实不能。

因为你必须知道删几个。

至少看一遍。复杂度：


xxxxxxxxxx
O(k)

已经最优。

真正 VS Code

其实已经不是：


xxxxxxxxxx
Tree

了。

而是：


xxxxxxxxxx
TreeStore
↓
expandedSet
↓
visibleNodes

Tree 只是数据库。

真正工作的一直都是：


xxxxxxxxxx
visibleNodes

面试加分点（很多人答不到）

如果面试官问：

为什么还要保留原始 Tree？为什么不只有 visibleNodes？

这是一个非常好的问题。

你的回答可以是：

English

The original tree is the source of truth. The visible list is only a projection of the tree based on the current expansion state. If I only keep the visible list, collapsing and re-expanding a node becomes difficult because I'd lose the hidden subtree structure. So in production, I keep both: the original tree stores the complete hierarchy, while the visible list is optimized for rendering.

中文

原始 Tree 是数据源（Source of Truth），而 visibleNodes 只是根据当前展开状态计算出来的一个视图。如果只保留 visibleNodes，收起节点后就丢失了被隐藏子树的层级关系，之后再展开会很麻烦。因此生产环境通常会同时保留完整 Tree 和 visibleNodes：前者负责保存完整结构，后者负责高效渲染。

不过，我会建议我们再往前走一步

到目前为止，我们已经是在写一个 Tree Widget。

真正的 Virtual Tree（像 VS Code Explorer、Figma Layers）还有一个更关键的优化：

为什么每次 expand 还要对当前子树执行一次 DFS？能不能连这一步都省掉？

答案是：可以。

很多成熟实现会在初始化时就建立DFS 顺序索引（Euler Tour / Preorder Index），这样展开和收起时可以直接定位连续区间，进一步减少遍历和计算。这一步已经涉及到高级数据结构，也是很多大型 UI 框架实现高性能 Tree 的关键。

我建议下一节就讲这个，因为它是真正把 Tree Virtualization 提升到“高级前端/架构级”实现的核心。

下一步

好，我们开始真正的高级版。

这一节是VS Code、Chrome DevTools、IDE 文件树都会用到的思想。

也是很多 Senior Frontend 面试官最喜欢问的一题。

先思考一个问题

我们现在 Expand：


xxxxxxxxxx
src
└── components
      ├── Button
      └── Modal

点击：


xxxxxxxxxx
components

还是会：


xxxxxxxxxx
flattenTree(children)

虽然不是 DFS 整棵树。但还是 DFS：


Button
Modal

如果：


xxxxxxxxxx
components
↓
100000 children

还是很慢。

有没有办法连 DFS 都不要？

答案：有。

真正的思想

很多 IDE 会把 Tree 预处理成：


xxxxxxxxxx
Tree
↓
DFS Order（Preorder）
↓
Array

例如：


xxxxxxxxxx
src
├── components
│   ├── Button
│   │    ├── index.ts
│   │    └── style.css
│   └── Modal
└── pages

初始化一次：

得到：

index	node
0	src
1	components
2	Button
3	index.ts
4	style.css
5	Modal
6	pages

有没有觉得眼熟？

这就是：

DFS 的访问顺序。

以后：永远不变。

为什么有用？

例如：

Button：


xxxxxxxxxx
Button
├── index.ts
└── style.css

DFS 顺序：


xxxxxxxxxx
Button
index.ts
style.css

是不是 Button 的整个子树一定连续？这是 DFS 的性质。

例如：


xxxxxxxxxx
0 src
1 components
2 Button
3 index.ts
4 style.css
5 Modal
6 pages

Button：

对应：


xxxxxxxxxx
2
↓
4

连续。

那 Expand 怎么办？

以前 Expand：


xxxxxxxxxx
Button
↓
DFS(Button.children)

现在不用。因为初始化已经知道：


xxxxxxxxxx
Button
↓
2~4

直接：


xxxxxxxxxx
allNodes.slice(3,5)

是不是连 DFS 都没有了。

怎么知道结束位置？

初始化 DFS 时：

记录：


xxxxxxxxxx
interface NodeMeta {
    preorderIndex:number
    subtreeSize:number
}

例如：


xxxxxxxxxx
Button
↓
preorder = 2
subtreeSize = 3

什么意思？

表示：


xxxxxxxxxx
Button
index.ts
style.css

一共：


xxxxxxxxxx
3

所以结束：


xxxxxxxxxx
2+3-1
=
4

是不是一下知道整个 subtree。

初始化

DFS除了：


xxxxxxxxxx
nodeMap

现在还记录：


xxxxxxxxxx
metaMap

例如：


xxxxxxxxxx
metaMap.set(node.id,{
    preorderIndex,
    subtreeSize
})

DFS 返回的时候：

计算：


xxxxxxxxxx
subtreeSize =
1 +
left +
right

Expand

以前：


xxxxxxxxxx
flattenTree(children)

现在：


xxxxxxxxxx
const meta =
metaMap.get(id)

例如：


xxxxxxxxxx
Button
↓
preorder=2
size=3

整个 subtree：

就是：


xxxxxxxxxx
allNodes.slice(
    3,
    5
)

然后插进去。

Collapse

还是扫描 depth。或者如果维护：


xxxxxxxxxx
visibleIndexMap

甚至可以直接知道删几个。

为什么 VS Code 很快？

因为初始化 DFS 一次以后，所有Expand都是：


xxxxxxxxxx
slice()
splice()

没有DFS。

不过……

这里我要停一下。

我并不建议你在项目里这样写。

为什么？

因为这里有一个隐藏 Bug。

假设：


xxxxxxxxxx
src
├── components（展开）
│   ├── Button（收起）
│   │    ├── index.ts
│   │    └── style.css
│   └── Modal
└── pages

如果：


xxxxxxxxxx
allNodes.slice(...)

会得到：


xxxxxxxxxx
Button
index.ts
style.css

但是 Button 其实没有展开。

真正应该显示：


xxxxxxxxxx
Button
Modal

所以你会发现：

仅仅记录 preorderIndex + subtreeSize 是不够的。

因为 Visible Tree 不是：


xxxxxxxxxx
DFS Tree

而是：


xxxxxxxxxx
DFS Tree
+
Expanded State

这是很多人第一次设计 Virtual Tree 时都会踩的坑。

真正生产环境怎么办？

真正的实现通常是：

保留一份完整的 DFS 顺序数组（allNodes）
每个节点维护 expanded 状态
展开时，从当前节点开始顺序扫描 DFS 数组，只把祖先都处于展开状态的节点加入 visibleNodes
收起时，从 visibleNodes 中删除对应后代

也就是说：


xxxxxxxxxx
AllNodes（完整 DFS 顺序）
            │
            ▼
Expanded Set
            │
            ▼
VisibleNodes（真正渲染）

这样既避免了重复遍历整棵树，又不会错误地显示那些祖先未展开的节点。

如果这是一次 Senior Frontend 面试，我会把这个总结成一句话：

Tree Virtualization isn't just about rendering fewer DOM nodes. The harder problem is efficiently maintaining the mapping between the tree structure and the visible linear list as nodes expand and collapse.

这句话通常会让面试官知道，你理解的重点已经不是“虚拟滚动”本身，而是数据结构的设计。这也是为什么成熟的 Tree 组件，真正复杂的代码往往不在 React，而是在维护 visibleNodes、expandedSet、各种索引和映射关系的数据层。

v4 版本最终代码

好，这里给你一份真正完整的 v4（生产思路版）Virtual Tree。

这一版的核心是：

❗ 不再 DFS whole tree ❗ 不再 flatten whole tree ❗ 只维护 visibleNodes + maps ❗ expand / collapse 是局部更新（O(k)）

目录结构


xxxxxxxxxx
src/
├── App.tsx
├── types.ts
├── data.ts
├── treeStore.ts
├── VirtualTree.tsx

1️⃣ types.ts


xxxxxxxxxx
export interface TreeNode {
  id: string;
  name: string;
  children?: TreeNode[];
}
export interface VisibleNode {
  id: string;
  name: string;
  depth: number;
  children?: TreeNode[];
}

2️⃣ data.ts


xxxxxxxxxx
import { TreeNode } from "./types";
export const treeData: TreeNode[] = [
  {
    id: "src",
    name: "src",
    children: [
      {
        id: "components",
        name: "components",
        children: [
          { id: "button", name: "Button.tsx" },
          { id: "modal", name: "Modal.tsx" },
        ],
      },
      {
        id: "pages",
        name: "pages",
        children: [
          { id: "home", name: "Home.tsx" },
          { id: "about", name: "About.tsx" },
        ],
      },
      { id: "pkg", name: "package.json" },
    ],
  },
];

3️⃣ treeStore.ts（⭐核心）

这一层就是“VS Code 思路”。


import { TreeNode, VisibleNode } from "./types";
export class TreeStore {
  private nodeMap = new Map<string, TreeNode>();
  private childrenMap = new Map<string, TreeNode[]>();
  private visibleNodes: VisibleNode[] = [];
  private expanded = new Set<string>();
  constructor(tree: TreeNode[]) {
    this.build(tree);
    // 初始展开 root
    const root = tree[0];
    this.expanded.add(root.id);
    this.visibleNodes = this.buildVisible(tree, 0);
  }
  // -------- init --------
  private build(tree: TreeNode[]) {
    const dfs = (node: TreeNode) => {
      this.nodeMap.set(node.id, node);
      this.childrenMap.set(node.id, node.children ?? []);
      node.children?.forEach(dfs);
    };
    tree.forEach(dfs);
  }
  // -------- build visible (only first time) --------
  private buildVisible(
    nodes: TreeNode[],
    depth: number
  ): VisibleNode[] {
    const res: VisibleNode[] = [];
    const dfs = (node: TreeNode, d: number) => {
      res.push({
        ...node,
        depth: d,
      });
      if (
        this.expanded.has(node.id) &&
        node.children
      ) {
        node.children.forEach((c) =>
          dfs(c, d + 1)
        );
      }
    };
    nodes.forEach((n) => dfs(n, depth));
    return res;
  }
  // -------- public API --------
  getVisible() {
    return this.visibleNodes;
  }
  // -------- expand (O(k)) --------
  expand(id: string) {
    if (this.expanded.has(id)) return;
    this.expanded.add(id);
    const index = this.visibleNodes.findIndex(
      (n) => n.id === id
    );
    if (index === -1) return;
    const node = this.nodeMap.get(id);
    if (!node?.children) return;
    const insertNodes = this.buildVisible(
      node.children,
      this.visibleNodes[index].depth + 1
    );
    this.visibleNodes.splice(
      index + 1,
      0,
      ...insertNodes
    );
  }
  // -------- collapse (O(k)) --------
  collapse(id: string) {
    if (!this.expanded.has(id)) return;
    this.expanded.delete(id);
    const index = this.visibleNodes.findIndex(
      (n) => n.id === id
    );
    if (index === -1) return;
    const baseDepth =
      this.visibleNodes[index].depth;
    let end = index + 1;
    while (
      end < this.visibleNodes.length &&
      this.visibleNodes[end].depth >
        baseDepth
    ) {
      end++;
    }
    this.visibleNodes.splice(
      index + 1,
      end - index - 1
    );
  }
  toggle(id: string) {
    if (this.expanded.has(id)) {
      this.collapse(id);
    } else {
      this.expand(id);
    }
  }
}

4️⃣ VirtualTree.tsx（Virtualization + UI）


xxxxxxxxxx
import { useEffect, useMemo, useState } from "react";
import { TreeNode } from "./types";
import { TreeStore } from "./treeStore";
const ROW_HEIGHT = 32;
const HEIGHT = 240;
const OVERSCAN = 5;
export default function VirtualTree({
  tree,
}: {
  tree: TreeNode[];
}) {
  const store = useMemo(
    () => new TreeStore(tree),
    [tree]
  );
  const [visible, setVisible] = useState(
    store.getVisible()
  );
  const [scrollTop, setScrollTop] =
    useState(0);
  const refresh = () =>
    setVisible([...store.getVisible()]);
  const start = Math.max(
    0,
    Math.floor(scrollTop / ROW_HEIGHT) -
      OVERSCAN
  );
  const end =
    start +
    Math.ceil(HEIGHT / ROW_HEIGHT) +
    OVERSCAN * 2;
  const slice = visible.slice(start, end);
  return (
    <div
      style={{
        height: HEIGHT,
        overflow: "auto",
        border: "1px solid #ddd",
      }}
      onScroll={(e) =>
        setScrollTop(e.currentTarget.scrollTop)
      }
    >
      <div
        style={{
          height: visible.length * ROW_HEIGHT,
          position: "relative",
        }}
      >
        {slice.map((node, i) => {
          const realIndex = start + i;
          const hasChildren =
            !!node.children?.length;
          return (
            <div
              key={node.id}
              onClick={() => {
                store.toggle(node.id);
                refresh();
              }}
              style={{
                position: "absolute",
                top: realIndex * ROW_HEIGHT,
                height: ROW_HEIGHT,
                lineHeight: `${ROW_HEIGHT}px`,
                left: node.depth * 16,
                cursor: "pointer",
                userSelect: "none",
              }}
            >
              {hasChildren
                ? "📁"
                : "📄"}{" "}
              {node.name}
            </div>
          );
        })}
      </div>
    </div>
  );
}

5️⃣ App.tsx


xxxxxxxxxx
import VirtualTree from "./VirtualTree";
import { treeData } from "./data";
export default function App() {
  return (
    <div style={{ padding: 40 }}>
      <VirtualTree tree={treeData} />
    </div>
  );
}

这一版你已经实现了什么？

你现在这个 Tree 已经具备：

✅ 生产级结构思想

TreeStore（类似 VS Code data layer）
visibleNodes（render layer）
expandedSet（state layer）

✅ 性能优化

❌ 不再 DFS 全树
❌ 不再重新 flatten
✅ expand O(k)
✅ collapse O(k)
✅ render O(window size)

✅ Virtualization

fixed height
overscan
absolute positioning
translate-less rendering

面试总结一句话（非常重要）

你可以这样收尾：

This implementation separates the tree into a data layer (TreeStore) and a view layer (visibleNodes). Instead of recomputing the whole tree on every interaction, we incrementally update the visible list in O(k) based on expand/collapse operations, and then apply standard list virtualization on top of it.

如果你下一步还想继续升级（建议）

我可以再带你做这三个“真正高级版本”：

🔥 v5（真实 IDE 级）

lazy loading children (async fetch)
placeholder node

🔥 v6（超大规模优化）

stable index map（O(1) lookup）
no findIndex
pointer-based insertion

🔥 v7（Figma / VSCode级）

keyboard navigation (↑ ↓ → ←)
focus management
aria tree accessibility