如何获取树形结构的所有路径数组？

本例中需要生成的5种路径格式如下：

[
  [{ 1: "2" }, { 3: "4" }],
  [{ 1: "2" }, { 3: "5" }],
  [{ 1: "6" }, { 7: "8" }],
  [{ 1: "6" }, { 7: "9" }, { 10: "11" }],
  [{ 1: "6" }, { 7: "9" }, { 10: "12" }],
]

对应的树形结构示意图：

你尝试用递归遍历嵌套对象，但无法生成上述格式的数组，当前代码如下：

const data = {
  "1": {
    "2": {
      "3": {
        "4": {},
        "5": {}
      }
    },
    "6": {
      "7": {
        "8": {},
        "9": {
          "10": {
            "11": {},
            "12": {}
          }
        }
      }
    }
  }
}

let list = [];

function iterate(object) {
    if( object !== null && typeof object == "object" ) {
        Object.entries(object).forEach(([key, value]) => {
            if( JSON.stringify(value) != JSON.stringify({})) {
                let obj = {};
                obj[key] = Object.keys(value)
                list.push(obj);
                iterate(value);
            }
        });
    }
}

iterate(data);

当前代码运行结果示意图：

解决方案 #

当前代码的问题在于仅收集了单个节点，没有追踪完整路径。要生成目标格式，需要在递归时维护当前路径，遍历到叶子节点时将完整路径存入结果数组。调整后的代码如下：

const data = {
  "1": {
    "2": {
      "3": {
        "4": {},
        "5": {}
      }
    },
    "6": {
      "7": {
        "8": {},
        "9": {
          "10": {
            "11": {},
            "12": {}
          }
        }
      }
    }
  }
}

const result = [];

function traverse(obj, currentPath) {
  Object.entries(obj).forEach(([key, value]) => {
    // 生成当前节点：{父键: 子键}
    const node = { [key]: Object.keys(value)[0] };
    const newPath = [...currentPath, node];
    
    // 判断当前节点是否是叶子节点的父节点（子节点为空对象）
    const hasLeafChildren = Object.values(value).every(child => Object.keys(child).length === 0);
    
    if (hasLeafChildren) {
      // 为每个叶子节点生成完整路径
      Object.keys(value).forEach(childKey => {
        const leafNode = { [Object.keys(value)[0]]: childKey };
        result.push([...newPath.slice(0, -1), leafNode]);
      });
    } else {
      // 继续递归遍历子节点
      traverse(value, newPath);
    }
  });
}

// 初始调用，从根节点开始，当前路径为空
traverse(data, []);

console.log(result);

关键逻辑说明 #

• 递归函数traverse通过currentPath参数实时追踪当前已遍历的路径节点。
• 每次遍历键值对时，生成符合要求的节点格式，并更新路径。
• 识别叶子节点的父节点：当某个节点的所有子节点都是空对象时，说明该节点的子节点是路径终点，此时为每个子节点生成完整路径并加入结果数组。
• 非叶子节点则继续递归深入，直到遍历到所有路径终点。

内容的提问来源于stack exchange，提问作者Yura Solokha