如何将树结构展平为数组数组

Question

给定这样的结构：

var node = { children: [] }

也就是说：

1. 它只有children财产。
2. 没有parent财产。
3. 没有nextSibling财产。

如何使用自上而下的方法构建一个带有所有叶节点路径的平面数组列表：

1. 该算法不使用任何辅助方法，仅使用纯 JavaScript。
2. 该算法在从顶部遍历树时构建数组。

所以这是一个示例数据：

var node = {
  item: 1,
  children: [
    {
      item: 2,
      children: [
        {
          item: 3,
          children: [
            {
              item: 4,
              children: []
            },
            {
              item: 5,
              children: []
            },
            {
              item: 6,
              children: [
                {
                  item: 7,
                  children: []
                },
                {
                  item: 8,
                  children: []
                },
                {
                  item: 9,
                  children: []
                }
              ]
            }
          ]
        },
        {
          item: 10,
          children: [
            {
              item: 11,
              children: []
            },
            {
              item: 12,
              children: [
                {
                  item: 13,
                  children: []
                },
                {
                  item: 14,
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

该函数应该返回：

[
  [1, 2, 3, 4],
  [1, 2, 3, 5],
  [1, 2, 3, 6, 7],
  [1, 2, 3, 6, 8],
  [1, 2, 3, 6, 9],
  [1, 2, 10, 11],
  [1, 2, 10, 12, 13],
  [1, 2, 10, 12, 14]
]

到目前为止，我的尝试是以下变体：

function aggregateNodes(node) {
  var stack = [node]
  var array = []
  while (stack.length) {
    var node = stack.pop()
    array.push(node.item)
    node.children.forEach(function(child){
      stack.push(child)
    })
  }
  return array
}

function aggregateNodesRecursive(node) {
  var array = [node.item]
  node.children.forEach(function(child){
    array.push(child.item)
    child.children.forEach(function(confusedNow){
      array.push(confusedNow.item)
      aggregateNodesRecursive(confusedNow)
    })
  })
  return array
}

Answer 1

递归方法是：

 function traverse(node, path = [], result = []){
     if(!node.children.length)
        result.push(path.concat(node.item));
     for(const child of node.children)
         traverse(child, path.concat(node.item), result);
     return result;
 }

或者一些 hacky ES6：

const traverse = node => 
  (node.children.length?[]:[[node.item]]).concat(...node.children.map(child => 
     traverse(child).map(arr => 
         [node.item].concat(arr)
      )
  ));

现在调用traverse(node)将返回所需的结果。