手柄君的小阁

个人私货聚集地

阿里春招5月初 前端实习生 笔试最后一题与某手柄的解

本文最后更新于 2018 年 5 月 11 日,其中的内容可能有所发展或发生改变,敬请注意。

以下题目为:阿里春招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
  })
}

以上,得到解答,满足三个测试用例,不过总感觉哪里不太对……总之先溜了……(逃

来一发吐槽