以下题目为:阿里春招5月初 前端实习生 笔试最后一题
题图来源 Andrew Andrew Neel on Unsplash
请使用 JavaScript 编写一个树的深度优先遍历函数(节点最深的最先访问到,依次类推),满足以下测试用例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | // 假设树的结构如下 const tree = [ { id: 1, name: '张三', children: [ { id: 2, name: '李四', children: [ { id: 5, name: '张五' } ] } ] }, { id: 6, name: '玛丽' } ] // 测试用例: // 1. 生成一颗新树,将所有节点的id,加1 console.log( treeMap(tree, node => { let newNode = { ...node } newNode.id = node.id + 1 return newNode }) ) // 打印的新树,应该与tree的结构一致,只是每个id自增1,老的tree,应该没有任何改动 // 2. 打印每个节点的id treeMap(tree, node => { console.log(node.id) return node }) // 应打印顺序应该是: 5,2,1,6 // 3. 对于非法输入,应直接返回第一个入参 console.log(treeMap(null)) // 输出null console.log(treeMap(tree, true /*不是函数*/)) //输出tree |
解析发现题目其实是要求我们构造一个名为"treeMap"的函数,实现类似Array的Map的作用
根据需求,这里我们需要去遍历一个树结构,提到遍历就像自然而然想到递归,
根据测试用例2,可知遍历顺序为首先被便利到的是 第一个节点的最深子节点,可得到对子节点的操作和遍历是早于父节点的。
根据测试用例3,对非法输入进行检测,如果输入两个参数,第一个不为对象或第二个不为函数,则认为是非法输入,那么可以在得到以下基本函数
1 2 3 4 5 6 7 | const treeMap = (tree, f) => { //对非法输入的过滤 if (typeof f !== 'function' || typeof tree !== 'object') { //console.log(typeof f) return tree } } |
然后查看原始tree的格式发现tree每一节点都为一个数组,包含多个子节点,那么在这里,可以使用ES6 Array的map方法进行遍历,
并且因为遍历子节点要优先于同级节点,那么在执行传入的function前先继续递归下一级节点,得到以下函数
1 2 3 4 5 6 7 8 9 10 11 12 | const treeMap = (tree, f) => { if (typeof f !== 'function' || typeof tree !== 'object') { //console.log(typeof f) return tree } return tree.map(node => { const children = treeMap(node.children, f) const newTree = f(node) newTree.children = children; return newTree }) } |
以上,得到解答,满足三个测试用例,不过总感觉哪里不太对……总之先溜了……(逃