树状编号数组的叶子节点路径值拼接问题求解

问题描述 #

给定一个键为树状编号的键值对数组，需要找出所有叶子节点的完整路径，并将路径上的对应值拼接成完整内容。

输入数组 #

inputArr = [
    ["1", "I can "], 
    ["1.1", "speak "],
    ["1.1.1", "English."], 
    ["1.1.2", "Chinese "], 
    ["1.1.2.1", "well."], 
    ["1.2", "eat noodles."],
    ["1.3", "play football."],
    ["2", "I "],
    ["2.1", "drink."],
    ["2.2", "sleep."],
    ["3", "I am the man."],
    ["4", "Hire me."]
]

期望输出 #

outputArr = [
    ["1.1.1", "I can speak English."],
    ["1.1.2.1", "I can speak Chinese well."],
    ["1.2", "I can eat noodles."],
    ["1.3", "I can play football."],
    ["2.1", "I drink."],
    ["2.2", "I sleep."],
    ["3", "I am the man."],
    ["4", "Hire me."]
]

输出说明 #

输入数组中的第一个叶子节点是"1.1.1"，其路径为："1"->"1.1"->"1.1.1"，将路径上的值拼接后得到："I can " + "speak " + "English."。

尝试的思路与代码 #

设想的算法 #

从数组末尾开始遍历：
若键长度为1，则为根父节点；
若上方的键长度>1，则为叶子节点，此时拆分键获取路径并拼接对应值。

尝试的代码 #

function getSentences(arr) {

  let outputArr = [],
    s = [],
    curr, next;

  for (let i = 0; i < arr.length - 1; i++) {
    curr = arr[i];
    next = arr[i + 1];

    if (curr[0].length == 1) {
      s.push(curr[1]);
      if (curr[0].length == next[0].length) outputArr.push([curr[0], s.join('')]);
    } else if (curr[0].length < next[0].length) {
      s.push(curr[1]);
    } else if (curr[0].length >= next[0].length) {
      outputArr.push([curr[0], s.join('') + curr[1]]);
      if (curr[0].length > next[0].length) {
        s.pop();
      }
    }
  }

  for (i = 0; s.length == next[0].length; i++) {
    s.pop()
  }
  s.push(next[1])
  outputArr.push([next[0], s.join('')])

  return outputArr

}


var inputArr = [
  ["1", "I can "],
  ["1.1", "speak "],
  ["1.1.1", "English."],
  ["1.1.2", "Chinese "],
  ["1.1.2.1", "well."],
  ["1.2", "eat noodles."],
  ["1.3", "play football."],
  ["2", "I "],
  ["2.1", "drink."],
  ["2.2", "sleep."],
  ["3", "I am the man."],
  ["4", "Hire me."]
];

var outputArr = getSentences(inputArr);
console.log(outputArr);

解决方案 #

算法思路 #

1. 构建映射表：将所有键值对存入对象，方便通过键快速查找对应值。
2. 识别叶子节点：遍历每个元素，判断当前节点是否为叶子——即不存在以当前键为前缀且层级更深的子节点。
3. 拼接路径内容：对每个叶子节点，拆分其键的层级路径，依次从映射表中取出对应值拼接成完整内容。

修正后的代码 #

function getLeafSentences(arr) {
    // 构建键到值的映射表，同时收集所有键
    const keyMap = {};
    const allKeys = arr.map(item => {
        keyMap[item[0]] = item[1];
        return item[0];
    });

    const output = [];

    for (const [currentKey, currentValue] of arr) {
        // 判断是否为叶子节点：没有其他键以当前键加"."开头
        const isLeaf = !allKeys.some(key => key !== currentKey && key.startsWith(`${currentKey}.`));
        
        if (isLeaf) {
            // 拆分当前键的完整路径层级
            const pathSegments = [];
            let tempKey = currentKey;
            while (tempKey) {
                pathSegments.unshift(tempKey);
                // 截取父节点键，如"1.1.1"变为"1.1"，直到为空
                tempKey = tempKey.substring(0, tempKey.lastIndexOf('.'));
            }
            // 拼接路径上的所有值
            const fullContent = pathSegments.map(seg => keyMap[seg]).join('');
            output.push([currentKey, fullContent]);
        }
    }

    return output;
}

// 测试代码
var inputArr = [
    ["1", "I can "],
    ["1.1", "speak "],
    ["1.1.1", "English."],
    ["1.1.2", "Chinese "],
    ["1.1.2.1", "well."],
    ["1.2", "eat noodles."],
    ["1.3", "play football."],
    ["2", "I "],
    ["2.1", "drink."],
    ["2.2", "sleep."],
    ["3", "I am the man."],
    ["4", "Hire me."]
];

var outputArr = getLeafSentences(inputArr);
console.log(outputArr);

代码说明 #

• 映射表：keyMap存储所有键值对应关系，allKeys收集所有键用于叶子节点判断。
• 叶子节点判断：通过startsWith(${currentKey}.)检查是否存在子节点，确保当前节点是路径终点。
• 路径拆分：循环截取键的前缀，逐步获取父节点键，得到完整路径层级。
• 内容拼接：遍历路径层级，从映射表中取出对应值拼接成完整内容，加入输出数组。

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