树形结构查询节点及最近父组织的JavaScript算法优化问题

你的代码卡顿的核心原因有两点：

• 使用forEach遍历树，该方法无法被中断，就算找到目标节点也会遍历完整棵树
• 找到目标后还要额外遍历两次路径数组提取组织和部门信息，增加了不必要的开销

优化实现 #

核心思路 #

遍历树的过程中直接维护当前最近的上级ORGANIZATION节点，找到目标节点后立刻终止所有遍历，直接返回结果，省去后续路径处理步骤。

完整代码 #

首先是优化后的查找函数：

/**
 * 查找目标节点及最近上级组织
 * @param {Array} tree 组织部门树
 * @param {Number} targetId 目标节点id
 * @returns {Object|null} { orgInfo, deptInfo }，未找到返回null
 */
function findNodeAndParentOrg(tree, targetId) {
  let result = null
  // 维护遍历过程中当前最近的上级组织节点
  let currentNearestOrg = null

  function dfs(nodes) {
    // 用for循环替代forEach，支持中断遍历
    for (let i = 0; i < nodes.length; i++) {
      const node = nodes[i]
      const isOrg = node.type === 'ORGANIZATION'
      const prevOrg = currentNearestOrg
      // 进入组织节点，更新最近上级组织缓存
      if (isOrg) currentNearestOrg = node

      // 命中目标节点，直接组装结果返回
      if (node.id === targetId) {
        result = isOrg 
          ? { orgInfo: node, deptInfo: null }
          : { orgInfo: currentNearestOrg, deptInfo: node }
        return true
      }

      // 递归搜索子节点，子节点命中则直接终止遍历
      if (node.children?.length) {
        const foundInChild = dfs(node.children)
        if (foundInChild) return true
      }

      // 回溯：离开组织节点时回退最近上级组织缓存
      if (isOrg) currentNearestOrg = prevOrg
    }
    return false
  }

  dfs(tree)
  return result
}

然后修改你的Redux selector：

const itemSelector = createSelector(
  [
    state => state.LookUpReducer.selectedItem,
    state => state.globalReducer.department_tree,
  ],
  (selectedItem, tree) => {
    if (!selectedItem?.id || !tree?.length) {
      return { orgInfo: null, deptInfo: null }
    }
    return findNodeAndParentOrg(tree, selectedItem.id) ?? { orgInfo: null, deptInfo: null }
  }
)

优化点说明 #

• 遍历可中断：替换forEach为普通for循环，找到目标后立刻逐层返回终止递归，无需遍历剩余节点，树越大性能提升越明显
• 省去冗余计算：遍历过程中直接维护最近上级组织缓存，无需存储完整路径、也不需要后续两次遍历路径提取信息，时间复杂度降低到最坏O(n)，最佳情况仅需遍历到目标节点所在路径即可
• 内存占用更低：无需存储全路径数组，仅维护单个当前组织变量即可

额外优化建议 #

如果你的组织树更新频率很低、查询频率很高，可以在树更新时提前生成id到{orgInfo, deptInfo}的哈希映射表，后续查询直接O(1)读取，完全省去遍历开销。

内容的提问来源于stack exchange，提问作者Quang Bình Đinh