javascript - 我如何弄平一片(森林)树木？

Question

我有一片任意高度的森林，大致像这样:

let data = [
  { "id": 2, "name": "AAA", "parent_id": null, "short_name": "A" },
  {
    "id": 10, "name": "BBB", "parent_id": null, "short_name": "B", "children": [
      {
        "id": 3, "name": "CCC", "parent_id": 10, "short_name": "C", "children": [
          { "id": 6, "name": "DDD", "parent_id": 3, "short_name": "D" },
          { "id": 5, "name": "EEE", "parent_id": 3, "short_name": "E" }
        ]
      },
      {
        "id": 4, "name": "FFF", "parent_id": 10, "short_name": "F", "children": [
          { "id": 7, "name": "GGG", "parent_id": 4, "short_name": "G" },
          { "id": 8, "name": "HHH", "parent_id": 4, "short_name": "H" }
        ]
      }]
  }
];

我正在尝试生成所有根到叶路径的表示，类似这样

[
  [
    {
      "id": 2,
      "name": "AAA"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 3,
      "name": "C"
    },
    {
      "id": 6,
      "name": "DDD"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 3,
      "name": "C"
    },
    {
      "id": 5,
      "name": "EEE"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 4,
      "name": "F"
    },
    {
      "id": 7,
      "name": "GGG"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 4,
      "name": "F"
    },
    {
      "id": 8,
      "name": "HHH"
    }
  ]
]

所以我写了下面的代码:

function flattenTree(node, path = []) {
    if (node.children) {
        return node.children.map(child => flattenTree(child, [...path, child]));
  } else {
    let prefix = path.slice(0, path.length - 1).map(n => ({ id: n.id, name: n.short_name }));
    let last = path[path.length - 1];
    return [...prefix, { id: last.id, name: last.name } ];
  }
}

let paths = data.map(n => flattenTree(n, [n]));

但是 paths 带有额外的嵌套，像这样:

[
  [
    {
      "id": 2,
      "name": "AAA"
    }
  ],
  [
    [
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 3,
          "name": "C"
        },
        {
          "id": 6,
          "name": "DDD"
        }
      ],
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 3,
          "name": "C"
        },
        {
          "id": 5,
          "name": "EEE"
        }
      ]
    ],
    [
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 4,
          "name": "F"
        },
        {
          "id": 7,
          "name": "GGG"
        }
      ],
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 4,
          "name": "F"
        },
        {
          "id": 8,
          "name": "HHH"
        }
      ]
    ]
  ]
]

我忘记了尝试解决此问题的许多方法，但看起来该算法确实不应产生额外的嵌套——或者我的眼睛现在太过交叉以至于看不到我的错误如果有人将手指放在上面。

有人可以帮忙吗？请随意阅读此 JSFiddle https://jsfiddle.net/png7x9bh/66/

Answer 1

额外的嵌套由 map 创建。 map 只是将结果包装成一个数组并返回它们，它并不关心是否在子节点上调用它。使用 reduce 和 concat(或 push，任何适合您的性能)将结果直接放入第一级数组:

let data = [{"id":2,"name":"AAA","parent_id":null,"short_name":"A"},{"id":10,"name":"BBB","parent_id":null,"short_name":"B","children":[{"id":3,"name":"CCC","parent_id":10,"short_name":"C","children":[{"id":6,"name":"DDD","parent_id":3,"short_name":"D"},{"id":5,"name":"EEE","parent_id":3,"short_name":"E"}]},{"id":4,"name":"FFF","parent_id":10,"short_name":"F","children":[{"id":7,"name":"GGG","parent_id":4,"short_name":"G"},{"id":8,"name":"HHH","parent_id":4,"short_name":"H"}]}]}];

function flattenTree(node, path = []) {
    let pathCopy = Array.from(path);
    pathCopy.push({id: node.id, name: node.name});
    if(node.children) {
        return node.children.reduce((acc, child) => acc.concat(flattenTree(child, pathCopy)), []);
    }
    return [pathCopy];
}

let result = data.reduce((result, node) => result.concat(flattenTree(node)), []);
console.log(JSON.stringify(result, null, 3));