JS树形节点查找：转字符串判断与递归遍历哪种效率更高？

待处理数据结构 #

当前使用的是带children字段的标准嵌套树形数组，结构如下：

elements = 
  [ { id: 'uuid',         children: [] } 
  , { id: 'uuid',         children: [] } 
  , { id: 'uuid',         children: 
      [ { id: 'uuid',     children: [] } 
      , { id: 'uuid',     children: 
          [ { id: 'uuid', children: [] } 
          , { id: 'uuid', children: [] } 
          ] 
        } 
      , { id: 'uuid',     children: [] } 
      ] 
    } 
  ]

两种对比实现方案 #

方案1：序列化子树为字符串预判后递归 #

逻辑为：当前节点ID不匹配时，先将子节点序列化为JSON字符串，通过includes判断目标ID是否存在于子树中，存在才进入递归。

function findElementById(id_, elements){
  for (el of elements){
    if(el.id == id_) return el
    if(JSON.stringify(el.children).includes(id_)) return findElementById(id, el.children)
  }
}

方案2：直接深度优先递归遍历 #

逻辑为：当前节点ID不匹配时，只要存在子节点就直接进入递归查找，找到结果逐层返回。

function findElementById(id_, elements){
  for (el of elements){
    if(el.id == id_) return el
    if(el.children.length > 0) result = findElementById(id, el.children)
    if (result) return result
  }
}

注：两份示例代码都存在基础语法问题：递归传入的id未定义（应为入参id_），方案2的result未声明会污染全局作用域，实际使用需要先修复。

核心问题明确答复 #

1. 序列化字符串预判的方案完全无法提升效率，性能远差于直接递归
   这个方案的核心逻辑误区在于：你以为通过预判减少了不必要的分支遍历，但JSON.stringify序列化整段子树的过程，本身就是一次对该节点下所有层级子节点的完整深度遍历——和你直接递归进入子节点查找的遍历成本完全一致，还要额外承担三类开销：
   • 序列化过程中字符串拼接、特殊字符转义的CPU开销
   • 生成超长JSON字符串的内存分配开销
   • includes扫描整个字符串匹配目标ID的二次遍历开销
     相当于为了判断某条路有没有你要找的东西，先把这条路从头到尾走了一遍记成笔记，再翻笔记确认要不要进去找，比直接进去找多花了两倍多的成本。
     此外这个方案还有逻辑硬伤：如果某个节点的非id字段（比如名称、描述属性）的值刚好和目标ID字符串重合，会触发误判，递归进入根本不含目标节点的分支，进一步浪费性能，极端情况会返回错误结果。
2. 大体量数据下的性能表现
   当树节点量级达到万级以上时，序列化方案的性能会出现断崖式下跌：
   • 序列化生成的JSON字符串体积随节点数线性增长，大字符串会频繁触发JS引擎的垃圾回收，内存占用可达原始数据的3-5倍
   • 每一层级的预判都会重复序列化下层所有子节点，极端不平衡的树结构下时间复杂度会退化到O(n²)，而直接递归的深度优先遍历始终保持稳定的O(n)时间复杂度，额外开销只有递归栈占用，性能差距可达数十倍甚至上百倍。
3. 高频查找场景的最优方案
   如果需要频繁在树上按ID查找节点，不要每次查找都做全树遍历，只需要在数据初始化阶段做一次全树遍历，构建id -> 节点引用的Map索引，后续所有查找都是O(1)时间复杂度，性能提升最明显：

   // 初始化时一次性构建索引
   function buildNodeIndex(elements, indexMap = new Map()) {
     for (const node of elements) {
       indexMap.set(node.id, node)
       if (node.children?.length) buildNodeIndex(node.children, indexMap)
     }
     return indexMap
   }
   const nodeIndex = buildNodeIndex(elements)
   // 查找直接读取，无需遍历
   const targetNode = nodeIndex.get(targetId)
   

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