数组转树

// 时间复杂度 O(n)
function listToTree(arr) {
    let tree = {}
    // key: id, value: node
    let map = {}
    for (const node of arr) {
        // 浅拷贝，存储对节点node的引用
        map[node.id] = node
    }
    for (const node of arr) {
        // 根节点，最后只返回根节点
        if (!node.parent) {
            tree = map[node.id]
        } else {
            // 在map结构内改造，使父子节点关系绑定
            map[node.parent].children = map[node.parent].children || []
            map[node.parent].children.push(map[node.id])
        }
    }

    return tree
}

// test case
console.log(listToTree(list))

树转数组

深度优先遍历

TIP

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如在遍历树结构时，从根节点出发，访问当前节点的子节点，直到没有子节点返回，返回时也会不断重复这个过程，直至所有节点都被遍历完成。

维基百科

递归

// 递归
function treeToListDFS(tree, list = []) {
    for (const treeNode of tree) {
        list.push(deleteChildrenProp(treeNode))
        if (treeNode.children && treeNode.children.length) {
            treeToListDFS(treeNode.children, list)
        }
    }   
    return list
}

// 工具函数：返回一个新对象，包含原节点除了children属性之外的所有属性
function deleteChildrenProp(treeNode) {
    if (!treeNode.children) {
        return treeNode
    }
    const res = {}
    Object.keys(treeNode).filter(k => k !== 'children').forEach(k => {
        res[k] = treeNode[k]
    })
    return res
}

循环

function treeToListDFS(tree) {
    const list = []
    const stack = [...tree]
    while (stack.length) {
        // 利用栈先进后出，来优先处理子元素，子元素都处理完后再向父级节点回溯
        let treeNode = stack.pop()
        list.push(deleteChildrenProp(treeNode))
        if (treeNode.children && treeNode.children.length) {
            // 深度优先：只要节点有子元素则不断将子元素入栈，直到所有子元素及后代元素都遍历结束。
            for (let i = treeNode.children.length - 1; i >= 0; i--) {
                stack.push(treeNode.children[i])
            }
        }
    }
    return list
}

广度优先遍历

TIP

广度优先遍历是一种由近及远的遍历方式。如从根节点出发，始终优先访问距离最近的节点，并一层层向外扩张。广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

维基百科

function treeToListBFS(tree) {
    const list = []
    const queue = [...tree]
    while (queue.length) {
        // 利用队列先进先出，会逐层遍历父级节点，后代元素会被入队等待遍历
        const treeNode = queue.shift()
        list.push(deleteChildrenProp(treeNode))
        if (treeNode.children && treeNode.children.length) {
            treeNode.children.forEach(n => {
                queue.push(n)
            })
        }
    }
    return list
}