Daily-Interview-Question
Daily-Interview-Question copied to clipboard
第 5 题:介绍下深度优先遍历和广度优先遍历,如何实现?
第五题问的是深度优先遍历和广度优先遍历,我是从dom节点的遍历来理解这个问题的
html代码
我将用深度优先遍历和广度优先遍历对这个dom树进行查找
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
/*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
return nodeList
}
let deepTraversal2 = (node) => {
let nodes = []
if (node !== null) {
nodes.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
nodes = nodes.concat(deepTraversal2(children[i]))
}
}
return nodes
}
// 非递归
let deepTraversal3 = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodes
}
输出结果
广度优先遍历
广度优先遍历 BFS 从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
let widthTraversal2 = (node) => {
let nodes = []
let stack = []
if (node) {
stack.push(node)
while (stack.length) {
let item = stack.shift()
let children = item.children
nodes.push(item)
// 队列,先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
for (let i = 0; i < children.length; i++) {
stack.push(children[i])
}
}
}
return nodes
}
输出结果
ps
仅个人理解,如果有错欢迎大家指出批评,一起进步
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
图
图是一种复杂的非线性结构,它由边(边Edge)和点(顶点Vertex)组成。一条边连接的两个点称为相邻顶点。
G = (V, E)
图分为:
- 有向图
- 无向图
本文探讨的是无向图
图的表示
图的表示一般有以下两种:
- 邻接矩阵:使用二维数组来表示点与点之间是否有边,如
arr[i][j] = 1
表示节点 i 与节点 j 之间有边,arr[i][j] = 0
表示节点 i 与节点 j 之间没有边 - 邻接表:邻接表是图的一种链式储存结构,这种结构类似树的子链表,对于图中的每一个顶点Vi,把所有邻接于Vi的顶点Vj链成一个单链表,这个单链表就是顶点Vi的邻接表,单链表一般由数组或字典结构表示。
创建图
下面声明图类,Vertex 用数组结构表示,Edge 用 map结构表示
function Graph() {
this.vertices = [] // 顶点集合
this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
this.vertices.push(v)
this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
let vEdge = this.edges.get(v)
vEdge.push(w)
let wEdge = this.edges.get(w)
wEdge.push(v)
this.edges.set(v, vEdge)
this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
var s = ''
for (var i=0; i<this.vertices.length; i++) {
s += this.vertices[i] + ' -> '
var neighors = this.edges.get(this.vertices[i])
for (var j=0; j<neighors.length; j++) {
s += neighors[j] + ' '
}
s += '\n'
}
return s
}
测试:
var graph = new Graph()
var vertices = [1, 2, 3, 4, 5]
for (var i=0; i<vertices.length; i++) {
graph.addVertex(vertices[i])
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
console.log(graph.toString())
// 1 -> 4 3
// 2 -> 3 5
// 3 -> 1 2
// 4 -> 1
// 5 -> 2
测试成功
图的遍历
两种遍历算法:
- 深度优先遍历
- 广度优先遍历
深度优先遍历(DFS)
深度优先遍历(Depth-First-Search),是搜索算法的一种,它沿着树的深度遍历树的节点,尽可能深地搜索树的分支。当节点v的所有边都已被探寻过,将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止,如果还有未被发现的节点,则选择其中一个未被发现的节点为源节点并重复以上操作,直到所有节点都被探寻完成。
简单的说,DFS就是从图中的一个节点开始追溯,直到最后一个节点,然后回溯,继续追溯下一条路径,直到到达所有的节点,如此往复,直到没有路径为止。
DFS 可以产生相应图的拓扑排序表,利用拓扑排序表可以解决很多问题,例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。
注意:深度DFS属于盲目搜索,无法保证搜索到的路径为最短路径,也不是在搜索特定的路径,而是通过搜索来查看图中有哪些路径可以选择。
步骤:
- 访问顶点v
- 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问
- 若此时途中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到所有顶点均被访问过为止
实现:
Graph.prototype.dfs = function() {
var marked = []
for (var i=0; i<this.vertices.length; i++) {
if (!marked[this.vertices[i]]) {
dfsVisit(this.vertices[i])
}
}
function dfsVisit(u) {
let edges = this.edges
marked[u] = true
console.log(u)
var neighbors = edges.get(u)
for (var i=0; i<neighbors.length; i++) {
var w = neighbors[i]
if (!marked[w]) {
dfsVisit(w)
}
}
}
}
测试:
graph.dfs()
// 1
// 4
// 3
// 2
// 5
测试成功
广度优先遍历(BFS)
广度优先遍历(Breadth-First-Search)是从根节点开始,沿着图的宽度遍历节点,如果所有节点均被访问过,则算法终止,BFS 同样属于盲目搜索,一般用队列数据结构来辅助实现BFS
BFS从一个节点开始,尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的,首先检查最靠近第一个节点的层,再逐渐向下移动到离起始节点最远的层
步骤:
- 创建一个队列,并将开始节点放入队列中
- 若队列非空,则从队列中取出第一个节点,并检测它是否为目标节点
- 若是目标节点,则结束搜寻,并返回结果
- 若不是,则将它所有没有被检测过的字节点都加入队列中
- 若队列为空,表示图中并没有目标节点,则结束遍历
实现:
Graph.prototype.bfs = function(v) {
var queue = [], marked = []
marked[v] = true
queue.push(v) // 添加到队尾
while(queue.length > 0) {
var s = queue.shift() // 从队首移除
if (this.edges.has(s)) {
console.log('visited vertex: ', s)
}
let neighbors = this.edges.get(s)
for(let i=0;i<neighbors.length;i++) {
var w = neighbors[i]
if (!marked[w]) {
marked[w] = true
queue.push(w)
}
}
}
}
测试:
graph.bfs(1)
// visited vertex: 1
// visited vertex: 4
// visited vertex: 3
// visited vertex: 2
// visited vertex: 5
测试成功
本文始发于我的博客:深度优先遍历与广度优先遍历
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
前端确实很少涉及算法。 这个我也只在做小游戏的时候有用到过
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
Dom树的遍历
@atheist1 非递归版的 deepTraversal3 实际上是广度优先的
@caihg 我也是这样想的
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
这其实是和公司的具体业务相关的,我们公司把在业务层背后抽象了一套树形结构的领域对象模型,整个项目里少不了折腾树的递归,这时候发现熟练掌握深度遍历和广度遍历就十分有用了。
@atheist1 宽搜还是写 queue 吧,stack 歧义太严重了
这个字打错了吧
写得非常好了,我之前也了解过这两个东西,@atheist1 ,代码通俗易懂,答案简单直观,非常棒
generator +Interator接口实现深度遍历
function *DFS(tree){
yield tree;
let children=tree.children;
if(children){
for(let i in children){
yield *DFS(children[i])
}
}
}
console.log([...DFS(tree)])
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)? 2.14补充 对象的深拷贝
前端确实很少涉及算法。 这个我也只在做小游戏的时候有用到过
问下大佬,有个旧的json 格式转成新的json格式
var old ={ "颜色":[ { "黄色":{ "尺码":[ { "XL":{ "形状":[ { "多边形":1 }, { "方形":2 } ] } }, { "M":{ "形状":[ { "方形":3 } ] } } ] } }, { "红色":{ "尺码":[ { "XL":{ "形状":[ { "多边形":1 }, { "方形":2 } ] } }, { "M":{ "形状":[ { "方形":3 } ] } } ] } } ] }
var new =[ { // priceId: 1, // price: 35.0, // "stock": 8, "attrValueList": [ { "attrKey": "颜色", "attrValue": "黄色", "attrCode": "1001" }, { "attrKey": "尺码", "attrValue": "xm", "attrCode": "2001" }, { "attrKey": "形状", "attrValue": "多边形", "attrCode": "3001" }
]
},
{
// priceId: 1,
// price: 35.0,
// "stock": 8,
"attrValueList": [
{
"attrKey": "颜色",
"attrValue": "黄色",
"attrCode": "1001"
},
{
"attrKey": "尺码",
"attrValue": "L",
"attrCode": "2001"
},
{
"attrKey": "形状",
"attrValue": "多边形",
"attrCode": "3001"
}
]
},
{
// priceId: 1,
// price: 35.0,
// "stock": 8,
"attrValueList": [
{
"attrKey": "颜色",
"attrValue": "黄色",
"attrCode": "1001"
},
{
"attrKey": "尺码",
"attrValue": "L",
"attrCode": "2001"
},
{
"attrKey": "形状",
"attrValue": "五边形",
"attrCode": "3001"
}
]
}
] 有方便的转换方法吗
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
数组扁平化
深度优先:找到一个节点后,把它的后辈都找出来,最常用递归法。 广度优先:找到一个节点后,把他同级的兄弟节点都找出来放在前边,把孩子放到后边,最常用 while
@atheist1 非递归版的 deepTraversal3 实际上是广度优先的
为啥是广度的啊?deepTraversal3 不是把当前节点的所有子节点遍历出来之后,在遍历下一个同胞节点吗?
第五题问的是深度优先遍历和广度优先遍历,我是从dom节点的遍历来理解这个问题的
html代码
我将用深度优先遍历和广度优先遍历对这个dom树进行查找
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
/*深度优先遍历三种方式*/ let deepTraversal1 = (node, nodeList = []) => { if (node !== null) { nodeList.push(node) let children = node.children for (let i = 0; i < children.length; i++) { deepTraversal1(children[i], nodeList) } } return nodeList } let deepTraversal2 = (node) => { let nodes = [] if (node !== null) { nodes.push(node) let children = node.children for (let i = 0; i < children.length; i++) { nodes = nodes.concat(deepTraversal2(children[i])) } } return nodes } // 非递归 let deepTraversal3 = (node) => { let stack = [] let nodes = [] if (node) { // 推入当前处理的node stack.push(node) while (stack.length) { let item = stack.pop() let children = item.children nodes.push(item) // node = [] stack = [parent] // node = [parent] stack = [child3,child2,child1] // node = [parent, child1] stack = [child3,child2,child1-2,child1-1] // node = [parent, child1-1] stack = [child3,child2,child1-2] for (let i = children.length - 1; i >= 0; i--) { stack.push(children[i]) } } } return nodes }
输出结果
广度优先遍历
广度优先遍历 BFS 从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
let widthTraversal2 = (node) => { let nodes = [] let stack = [] if (node) { stack.push(node) while (stack.length) { let item = stack.shift() let children = item.children nodes.push(item) // 队列,先进先出 // nodes = [] stack = [parent] // nodes = [parent] stack = [child1,child2,child3] // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2] // nodes = [parent,child1,child2] for (let i = 0; i < children.length; i++) { stack.push(children[i]) } } } return nodes }
输出结果
ps
仅个人理解,如果有错欢迎大家指出批评,一起进步
感谢楼主的回答,了解到了深度遍历和广度遍历区别,小白把代码放在codepen实现了一遍。https://codepen.io/valleylmh/pen/EBBrWg
二叉树
var myTree = {
val: 6,
left: {
val: 5,
left: {
val: 4
},
right: {
val: 3
}
},
right: {
val: 2,
right: {
val: 1
}
}
}
广度优先遍历 BFS
思路是利用队列,从根节点开始,依次将左节点、右节点push进数组。
function bfs (tree) {
var queue = [tree]
var res = []
var count = 0
while (queue[count] && queue[count].val) {
res.push(queue[count].val)
var left = queue[count].left
var right = queue[count].right
if (left) {
queue.push(left)
}
if (right) {
queue.push(right)
}
count++
}
return res
}
深度优先遍历 DFS
思路是利用栈,从根节点开始,依次将右、左节点入栈。
// 非递归版本
function dfs (tree) {
var stack = [tree]
var res = []
while (stack.length) {
var node = stack.pop()
res.push(node.val)
var left = node.left
var right = node.right
if (right) stack.push(right)
if (left) stack.push(left)
}
return res
}
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
深拷贝感觉是用到了深度优先, 广度优先,我还没写过...我得研究下
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)? 2.14补充 对象的深拷贝
深拷贝感觉是用到了深度优先, 广度优先,我还没写过...我得研究下
从掘金的广度深拷贝问题过来的,结果全是在聊遍历,自己试着实现了一下广度拷贝,不知道有没有更好的方式。
const isArray = (a)=>{Array.isArray(a)};
const isObject = (o)=>Object.prototype.toString.call(o) === '[object Object]';
/**
* 广度优先深拷贝,借助队列实现,每个子节点入队列时,记录下它的新父节点以及他的key
*/
const bfsCopy = (src)=>{
const queue = [];
// 入队列操作
const inQueue = (o,parent) => {
for(let key in o){
queue.push({
parent, // 新的父节点
key, // 子节点的key
node: o[key] // 子节点
})
}
}
if(isArray(src) || isObject(src)){
const root = isArray(src) ? [] : {};
// 将根节点的子节点入队列
inQueue(src,root);
// 开始遍历队列
while(queue.length !== 0){
// 取出队头元素
const { parent, key , node } = queue.shift();
if(isArray(node) || isObject(node)){
const r = isArray(node) ? [] : {};
parent[key] = r;
inQueue(node,r)
}else{
parent[key] = node;
}
}
return root;
}
return src;
}
@atheist1 非递归版的 deepTraversal3 实际上是广度优先的
这个是深度优先的,你看看它最后的循环,是从末尾开始,也就是说,再下一次循环进来的时候,每次出栈都是从后面最后一个开始[其实已经到了子节点的范畴了】,[(当前节点的子节点是被放在栈的后面)
感觉广度优先遍历使用的stack 应该使用queue 更合适吧 就是先push进去的 先shift()取出来 放在nodes里
第五题问的是深度优先遍历和广度优先遍历,我是从dom节点的遍历来理解这个问题的
html代码
我将用深度优先遍历和广度优先遍历对这个dom树进行查找
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。 假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
/*深度优先遍历三种方式*/ let deepTraversal1 = (node, nodeList = []) => { if (node !== null) { nodeList.push(node) let children = node.children for (let i = 0; i < children.length; i++) { deepTraversal1(children[i], nodeList) } } return nodeList } let deepTraversal2 = (node) => { let nodes = [] if (node !== null) { nodes.push(node) let children = node.children for (let i = 0; i < children.length; i++) { nodes = nodes.concat(deepTraversal2(children[i])) } } return nodes } // 非递归 let deepTraversal3 = (node) => { let stack = [] let nodes = [] if (node) { // 推入当前处理的node stack.push(node) while (stack.length) { let item = stack.pop() let children = item.children nodes.push(item) // node = [] stack = [parent] // node = [parent] stack = [child3,child2,child1] // node = [parent, child1] stack = [child3,child2,child1-2,child1-1] // node = [parent, child1-1] stack = [child3,child2,child1-2] for (let i = children.length - 1; i >= 0; i--) { stack.push(children[i]) } } } return nodes }
输出结果
广度优先遍历
广度优先遍历 BFS 从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
let widthTraversal2 = (node) => { let nodes = [] let stack = [] if (node) { stack.push(node) while (stack.length) { let item = stack.shift() let children = item.children nodes.push(item) // 队列,先进先出 // nodes = [] stack = [parent] // nodes = [parent] stack = [child1,child2,child3] // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2] // nodes = [parent,child1,child2] for (let i = 0; i < children.length; i++) { stack.push(children[i]) } } } return nodes }
输出结果
ps
仅个人理解,如果有错欢迎大家指出批评,一起进步
所有的方法都缺少对 node.chilren的非空判断,如果对象没有children属性则会报错
深度优先遍历
遍历结果是: 1->2->4->8->5->3->6->7 广度优先遍历 遍历结果是:1->2->3->4->5->6->7->8
宽度优先遍历 和 深度优先遍历 是 遍历
或者 搜索
图 和 树 的算法。
深度优先遍历: 从根节点开始,沿着树的深度遍历树的节点,尽可能深的搜索树的分支。沿着一条可能的路径一直往下走,深入到不能深入为止。【可以纵向优先搜索】
宽度优先遍历: 从根节点开始,沿着树的宽度遍历树的节点。横向一层(level)的去遍历。
一楼大兄弟的html代码:
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
a
</div>
<div class="child-1-1-2">
b
</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">
c
</div>
</div>
<div class="child-1-3">
d
</div>
</div>
<div class="child-2">
<div class="child-2-1">
e
</div>
<div class="child-2-2">
f
</div>
</div>
<div class="child-3">
<div class="child-3-1">
g
</div>
</div>
</div>
深度优先遍历 - 递归
var dfs_recursive = function(root, res = []){
res.push(root)
for (let item of root.children) {
dfs_recursive(item, res)
}
return res
}
console.log('1------------->>', dfs_recursive(root))
深度优先遍历 - stack 先进后出 【push(item) -> pop】 或者 [unshift(item) -> shift()]
var dfs_stack = function(root) {
const res = []
const stack = []
stack.push(root)
while (stack.length != 0) {
let item = stack.pop()
res.push(item)
for (let i = item.children.length - 1; i >= 0; i--) {
stack.push(item.children[i])
}
}
return res
}
console.log('2------------->>', dfs_stack(root))
广度优先遍历 - queue 先进先出[push(item) -> shift()] 或者[unshift(item) -> pop()]
var bfs_queue = function(root) {
const res = []
const queue = []
queue.push(root)
while (queue.length != 0) {
let currentLevelLength = queue.length
for (let i = 0 ; i < currentLevelLength; i++) {
let item = queue.shift()
res.push(item)
for (let j = 0; j < item.children.length; j++) {
queue.push(item.children[j])
}
}
}
return res
}
console.log('3------------->>', bfs_queue(root))
深度遍历
var deep=(node,fn)=>{
fn(node);
if(node.children){
for(let i=0;i<node.children.length;i++){
deep(node.children[i],fn);
}
}
};
广度遍历
var wide=(node,fn)=>{
var queue = [];
queue.push(node);
while (queue.length != 0) {
let item = queue.shift();
fn(item);
for (let j = 0; j < item.children.length; j++) {
queue.push(item.children[j])
}
}
};
测试代码
var parent=document.getElementsByClassName('parent')[0];
wide(parent,(node)=>{
console.log(node.className);
});
deep(parent,(node)=>{
console.log(node.className);
});
我看大家广度优先都用两个数组做,其实用一个就可以了 ,利用for循环每次计算length的特性 广度优先遍历 `
function widthTraversal(node,nodeList = []){
if(!node){
return []
}
nodeList.push(node)
for(let a = 0; a<nodeList.length;a++){
let thisNode = nodeList[a]
for(let i = 0; i< thisNode.children.length; i++){
nodeList.push(thisNode.children[i])
}
}
return nodeList
}
`
我举个通俗的例子 假如你的面前摆了一排杯子,每个杯子里都装了不确定量的水。
深度优先遍历就是你拿起第一个杯子,喝光水,然后再拿起下一个杯子,喝光,一直到最后一个杯子。
广度优先遍历就是你从第一个杯子开始,每个杯子挨个都喝一口,然后又重头开始挨个喝一口,一直到全部喝完为止。
是这样吧?
概念上我觉得没啥问题,具体在业务上有啥应用的地方吗(尤其是前端)?
2.14补充 对象的深拷贝
遍历树型结构对象啊
const data = [{
name: 'a',
children: [{
name: 'a1',
children: [{
name: 'a11'
}, {
name: 'a12'
}]
}, {
name: 'a2',
children: [{
name: 'a21'
}, {
name: 'a22'
}]
}, {
name: 'a3',
children: [{
name: 'a31'
}, {
name: 'a32'
}]
}, ],
}, {
name: 'b',
children: [{
name: 'b1',
children: [{
name: 'b11'
}, {
name: 'b12'
}]
}, {
name: 'b2',
children: [{
name: 'b21'
}, {
name: 'b22'
}]
}, {
name: 'b3',
children: [{
name: 'b31'
}, {
name: 'b32'
}]
}, ],
}];
let result = [];
// 深度遍历
function deep(ary) {
for (const val of ary) {
result.push(val.name);
if (Array.isArray(val.children)) {
deep(val.children);
}
}
return result.join(',');
}
// const str = deep(data);
// 广度遍历
function bfs(ary) { // 对比了下楼上的,我发现我这运行效率有点低,233333
let quee = [];
for (let i = 0; i < ary.length; i++) {
result.push(ary[i].name);
if (Array.isArray(ary[i].children)) {
quee.push(...ary[i].children);
if (i === ary.length - 1) {
bfs(quee);
}
}
}
return result.join(',');
}
const str = bfs(data);
console.log(str);