树的遍历如何改写尾递归TCO

Question

已经写好一个遍历树的方法，该方法将树形数组扁平化成只有一级的数组，且带有层级计数、深度优先，但考虑到层级可能较多，希望能使用TCO优化，百思不得其解，希望各位指点一下。
已有树遍历代码如下：

function parseFlat(data, _level = 0) {
    let result = []
    // 层级计数
    _level++
    for (const _data of data) {
        const junior = _data.children
        // 当前节点是否为叶子节点
        const _isLeaf = !Array.isArray(junior)
        result.push({ _data, _level, _isLeaf })
        if (!_isLeaf) {
            // 拼接下级
            result = result.concat(
                parseFlat(junior, _level)
            )
        }
    }
    return result
}
const tree = [{
    name: 'A',
    children: [{
        name: 'a',
        children: [{
            name: 'aa'
        }]
    }]
},
{
    name: 'B',
    children: [{
        name: 'b',
        children: [{
            name: 'bb'
        }]
    }]
}]
console.log(JSON.stringify(parseFlat(tree)))))
/*
[{
    "_data": {
        "name": "A",
        "children": [{
            "name": "a",
            "children": [{
                "name": "aa"
            }]
        }]
    },
    "_level": 1,
    "_isLeaf": false
},
{
    "_data": {
        "name": "a",
        "children": [{
            "name": "aa"
        }]
    },
    "_level": 2,
    "_isLeaf": false
},
{
    "_data": {
        "name": "aa"
    },
    "_level": 3,
    "_isLeaf": true
},
{
    "_data": {
        "name": "B",
        "children": [{
            "name": "b",
            "children": [{
                "name": "bb"
            }]
        }]
    },
    "_level": 1,
    "_isLeaf": false
},
{
    "_data": {
        "name": "b",
        "children": [{
            "name": "bb"
        }]
    },
    "_level": 2,
    "_isLeaf": false
},
{
    "_data": {
        "name": "bb"
    },
    "_level": 3,
    "_isLeaf": true
}]
*/

Answer 1

递归基本就你实现的这样，不过可以再简洁一点。
用循环改写的话，也很好理解，就是每个节点原地爆炸把子元素扩展出来，其实就是手动递归了。

这个递归好像并不能改为尾递归（即不能依赖解释器来优化），所以手动维护列表来转为循环。

//递归实现
function treeToList (tree, result = [], level = 1) {
    tree.forEach(node => {
      result.push(node)
      node.level = level++
      node.children && treeToList(node.children, result, level)
    })
    return result
}
// 循环实现
function treeToList (tree) {
  let result = tree.map(node => (node.level = 1, node))
  for (let i = 0; i < result.length; i++) {
    if (!result[i].children) continue
    let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
    result.splice(i+1, 0, ...list)
  }
  return result
}