树形编号列表数组的叶子节点路径生成及特殊规则处理

输入输出示例 #

输入数组 #

const inputArr = [
  ["1", "p"], 
  ["1.1", "q"], 
  ["1.2", "a"], 
  ["1.2", "b"], 
  ["1.2", "c"], 
  ["1.2.1", "d"], 
  ["1.2.2", "4"], 
  ["1.2.2.1", "5"], 
  ["1.3", "6"], 
  ["1.4x", "7"], 
  ["2", "8"], 
  ["2.1", "9"], 
  ["2.2", "10"], 
  ["2.2.1x", "11"],
  ["2.2.2", "12"],
  ["3", "13"], 
  ["4", "14"]
];

预期输出数组 #

const outputArr = [
  ["1.1", "p,q"], 
  ["1.2.1", "p,a,b,c,d"], 
  ["1.2.2.1", "p,a,b,c,4,5"], 
  ["1.3", "p,6"], 
  ["1.4x", "7"], // 不拼接父节点值，因键尾部带x
  ["2.1", "8,9"], 
  ["2.2.1x", "11"], // 不拼接父节点值，因键尾部带x
  ["2.2.2", "8,10,12"],
  ["3", "13"], 
  ["4", "14"]
];

规则说明 #

• 重复键需合并对应值：如["1.2","a"],["1.2","b"],["1.2","c"]需合并为["1.2","a,b,c"]
• 键尾部带x的叶子节点：不继承父路径的对应值，仅保留自身值
• 生成叶子节点完整路径值：非带x的叶子节点，需拼接从根到自身路径上所有节点的合并值，用逗号分隔

算法思路 #

1. 合并重复键：遍历输入数组，用对象存储每个键对应的合并值，遇到重复键则追加值（用逗号分隔）。
2. 构建层级树：将合并后的键按.分割为层级片段，逐个插入树形结构，每个节点保存键、值、子节点列表，同时标记是否为带x节点。
3. 识别叶子节点：遍历树结构，找出没有子节点的节点（叶子）。
4. 生成路径结果：
   • 带x的叶子：直接输出[键, 自身值]
   • 非带x的叶子：从根节点到当前叶子的路径上，依次收集所有节点的值并拼接，输出[键, 拼接后的字符串]

修正后的JavaScript实现代码 #

function getTreeBranch(inputArr) {
  // 步骤1：合并重复键的值
  const keyValueMap = {};
  inputArr.forEach(([key, value]) => {
    if (keyValueMap[key]) {
      keyValueMap[key] += `,${value}`;
    } else {
      keyValueMap[key] = value;
    }
  });

  // 步骤2：构建树形结构
  const tree = {};
  const allKeys = Object.keys(keyValueMap);
  
  allKeys.forEach(key => {
    const parts = key.split('.');
    let currentNode = tree;
    let currentPath = '';

    parts.forEach((part, index) => {
      const isLastPart = index === parts.length - 1;
      currentPath = currentPath ? `${currentPath}.${part}` : part;

      if (!currentNode[part]) {
        currentNode[part] = {
          key: currentPath,
          value: keyValueMap[currentPath],
          children: {},
          isXNode: currentPath.endsWith('x')
        };
      }

      currentNode = currentNode[part].children;
    });
  });

  // 步骤3：遍历树，收集所有叶子节点并生成结果
  const output = [];

  function traverse(node) {
    // 判断是否为叶子节点：没有子节点
    const isLeaf = Object.keys(node.children).length === 0;
    if (isLeaf) {
      if (node.isXNode) {
        output.push([node.key, node.value]);
      } else {
        // 回溯收集路径上的所有值
        const pathValues = [];
        let currentKey = node.key;
        while (currentKey) {
          pathValues.unshift(keyValueMap[currentKey]);
          // 去掉最后一个层级，得到父键
          const lastDotIndex = currentKey.lastIndexOf('.');
          currentKey = lastDotIndex !== -1 ? currentKey.slice(0, lastDotIndex) : null;
        }
        output.push([node.key, pathValues.join(',')]);
      }
      return;
    }
    // 递归遍历子节点
    Object.values(node.children).forEach(child => traverse(child));
  }

  // 遍历根节点的所有子节点
  Object.values(tree).forEach(rootChild => traverse(rootChild));

  return output;
}

// 测试调用
const result = getTreeBranch(inputArr);
console.log(result);

代码说明 #

• 合并重复键：通过keyValueMap对象快速去重并合并值，时间复杂度O(n)，n为输入数组长度。
• 树形构建：按键的层级片段逐步插入节点，确保每个层级的节点都被正确关联。
• 叶子节点处理：通过递归遍历识别叶子，带x节点直接输出，非带x节点通过回溯父键拼接路径值，确保路径完整。

内容的提问来源于stack exchange，提问作者Imran Al Rashid