FAANG面试题：实现DOM树指定属性匹配的Trie优化JS函数

问题分析 #

常规BFS/DFS遍历DOM的痛点是，每次都要重复解析元素颜色值并做等价判断，DOM节点量极大时效率偏低。用Trie可以提前把所有同义颜色值做映射，快速判断元素颜色是否属于目标颜色的等价集合，避免重复的颜色转换逻辑。

核心思路 #

1. 构建颜色同义Trie树：将目标颜色的所有等价表示（如white、#fff、#ffffff、rgb(255,255,255)等）插入Trie。
2. DOM遍历+颜色匹配：遍历DOM时提取元素计算样式的颜色值，转成标准化格式后在Trie中查询，匹配成功则加入结果数组。

实现代码 #

1. Trie节点与Trie类 #

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class ColorTrie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(colorStr) {
    let current = this.root;
    for (const char of colorStr) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isEnd = true;
  }

  search(colorStr) {
    let current = this.root;
    for (const char of colorStr) {
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    return current.isEnd;
  }
}

2. 颜色标准化工具 #

把不同格式的颜色转成统一的RGB字符串，确保Trie匹配的一致性：

function normalizeColor(color) {
  const tempEl = document.createElement('div');
  tempEl.style.color = color;
  document.body.appendChild(tempEl);
  const computedColor = getComputedStyle(tempEl).color;
  document.body.removeChild(tempEl);

  // 忽略透明度，只匹配纯色值
  if (computedColor.startsWith('rgba')) {
    return computedColor.replace(/rgba\((\d+),\s*(\d+),\s*(\d+),\s*\d+\)/, 'rgb($1,$2,$3)');
  }
  return computedColor;
}

3. 构建目标颜色的同义Trie #

function buildColorTrie(targetColor) {
  const trie = new ColorTrie();
  const normalizedTarget = normalizeColor(targetColor);
  
  trie.insert(normalizedTarget);

  // 扩展常见颜色的同义映射，可按需添加更多
  const colorSynonyms = {
    'rgb(255,255,255)': ['white', '#fff', '#ffffff', 'rgb(255,255,255)', 'rgba(255,255,255,1)'],
    'rgb(0,0,0)': ['black', '#000', '#000000', 'rgb(0,0,0)', 'rgba(0,0,0,1)']
  };

  if (colorSynonyms[normalizedTarget]) {
    colorSynonyms[normalizedTarget].forEach(color => {
      trie.insert(normalizeColor(color));
    });
  }

  return trie;
}

4. 主函数：DOM遍历与匹配 #

function findAllEle(prop, targetColor) {
  const result = [];
  const colorTrie = buildColorTrie(targetColor);

  // DFS遍历DOM树
  function traverse(node) {
    if (!node) return;
    if (node.nodeType === Node.ELEMENT_NODE) {
      const computedProp = getComputedStyle(node)[prop];
      const normalizedProp = normalizeColor(computedProp);
      if (colorTrie.search(normalizedProp)) {
        result.push(node);
      }
    }
    for (const child of node.childNodes) {
      traverse(child);
    }
  }

  traverse(document.body);
  return result;
}

优化说明 #

• Trie查询的时间复杂度为O(k)（k为颜色字符串长度），相比每次做字符串全等判断或哈希表查询，在大DOM场景下效率更高。
• 颜色标准化解决了不同格式同义颜色的匹配问题，避免漏判。
• 可通过扩展colorSynonyms对象，覆盖更多常见颜色的同义表示。

内容的提问来源于stack exchange，提问作者seyet