乐闻世界logo
5月28日 03:13

如何用 JavaScript 广度优先遍历 DOM 树？

用队列。从根节点入队，每次出队一个节点处理，再把它的子节点依次入队，循环到队列为空。

javascript
function bfsTraverse(root) {
  if (!root) return;
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.tagName);
    for (const child of node.children) {
      queue.push(child);
    }
  }
}

面试官问这道题，考的是你对树形结构和队列的理解——DOM 是棵树，BFS 用队列逐层扩展，DFS 用栈先钻到底。别搞混数据结构就行。

追问

BFS 和 DFS 在 DOM 上各自适合什么场景？

BFS 适合找离根近的节点——比如页面第一个 <article> 标签。DFS 适合找深层嵌套的元素，比如 <head> 里的 <meta>。日常用的 querySelector 浏览器内部走的就是 DFS 前序遍历。

shift() 的性能问题怎么解决？

Array.prototype.shift() 是 O(n)，每次都要移动剩余元素。节点多的时候拖慢整体。两个解法：

索引队列（推荐面试写法）：

javascript
function bfsTraverse(root) {
  if (!root) return;
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    for (const child of node.children) queue.push(child);
  }
}

链表队列：生产环境更稳，但面试写起来费时间，提到就行。

实际面试直接写 shift() 版本没问题，能顺嘴提到这个优化点就够了。

node.children 和 node.childNodes 有什么区别？

children 只返回元素节点（Element），childNodes 返回所有节点包括文本节点、注释节点。BFS 遍历 DOM 树通常用 children，除非你明确要处理文本节点。

时间和空间复杂度？

时间 O(n)，每个节点入队出队各一次。空间 O(w)，w 是树的最大宽度——最宽那一层有多少个节点。完全二叉树最宽层约 n/2 个节点，所以最坏空间也是 O(n)。

真实项目里什么时候会手写 DOM 遍历？

很少。浏览器提供了 querySelectorAll、TreeWalker、NodeIterator 等原生 API，绝大多数场景不需要手写遍历。但面试考这个是在验证你对数据结构的基本功，就像问快排不是为了让你手写排序，而是看你懂不懂分治思想。

标签：JavaScript前端