最近碰到一个面试题，如何实现深度遍历和广度遍历，深度遍历我们常用，但是广度遍历会少一点，不知道的同学可以一起学习一下，知道的就当巩固知识点吧
先说下区别
| 名称 | 采用 | 区别 |
|---|---|---|
| 深度优先遍历 | 递归 | 不需要记住所有的节点, 所以占用空间小 |
| 广度优先遍历 | 队列 | 需要先记录所有的节点占用空间大 |
/* 要使用到的数组，我们来遍历获得name */
let data = [
{
name: 'A-1',
children: [
{
name: 'A-2-2'
},
{
name: 'A-2-2',
children: [
{
name: 'A-3-1',
children: [
{
name: 'A-4-1'
},
{
name: 'A-4-2'
}
]
},
{
name: 'A-3-2'
}
]
}
]
},
{
name: 'B-1'
},
{
name: 'C-1',
children: [
{
name: 'C-2-1'
},
{
name: 'C-2-2'
},
]
}
]
使用递归实现深度遍历，先进后出，形似栈
function depth(dt) {
let result = []
let mp = data => {
data.forEach(item => {
result.push(item.name)
item.children && mp(item.children)
})
}
mp(dt)
return result
}
console.log('｜深度遍历------')
console.log(depth(data))
使用队列形式，先进先出，形似堆
/* queue.push(...curt.children)相当于 (queue = [...queue, ...curt.children]) */
function span(dt) {
let result = []
let queue = [...dt]
while (queue.length > 0) {
let curt = queue.shift()
result.push(curt.name)
curt.children && queue.push(...curt.children)
}
return result
}
console.log('｜广度遍历------')
console.log(span(data))
输入结果如下图
image.png
对比一下不同，这回应该都明白了吧
