如何高效统计嵌套规则结构中每个父节点下的condition总数量

问题背景 #

现有嵌套规则结构如下：

const mainQuery = [
{
  id: 1,
  type: "and",
  rules: [
    { id: 2, type: "condition", rules: 1 },
    { id: 3, type: "condition", rules: 2 },
    {
      id: 4,
      type: "and",
      rules: [
        { id: 5, type: "condition", rules: 3 },
        {
          id: 6,
          type: "and",
          rules: [
            { id: 7, type: "condition", rules: 4 },
            { id: 8, type: "condition", rules: 5 }
          ]
        }
      ]
    },
    {
       id: 9,
       type: "and",
       rules: [
         { id: 10, type: "condition", rules: 6 },
         { id: 11, type: "condition", rules: 7 }
       ]
     }
  ]
}];

需要统计每个父节点下包含的所有condition类型节点的总数量，要求避免多次循环遍历。

最优解决方案 #

用单次深度优先遍历（DFS） 即可完成全量统计，时间复杂度为O(n)，n为所有节点总数量，全程仅遍历一次所有节点，无重复计算。
遍历逻辑如下：

1. 遇到condition类型节点直接返回计数1
2. 遇到and等逻辑类型节点，遍历其所有子规则累加计数，将最终计数挂载到当前节点的属性上，再返回该计数值

实现代码 #

function calcConditionCount(node) {
  // 条件节点直接返回计数1
  if (node.type === 'condition') return 1

  let total = 0
  for (const childNode of node.rules) {
    total += calcConditionCount(childNode)
  }
  // 统计结果挂载到节点，后续直接取用无需二次计算
  node.conditionTotal = total
  return total
}

// 调用入口，执行一次即可完成所有节点统计
calcConditionCount(mainQuery[0])

结果验证 #

执行完成后直接读取节点上挂载的conditionTotal属性即可：

• mainQuery[0].conditionTotal 输出为 7
• mainQuery[0].rules[2].conditionTotal 输出为 3

如果担心嵌套层级过深导致递归栈溢出，可以将递归实现改为迭代版DFS，逻辑完全一致，遍历效率不变。

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