这个也是最近遇到的题目
深度优先搜索
实现一个深度优先搜索算法(非递归)
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
function dfs(tree, name){
// 请在这里实现
}
var tree = {
name : '中国',
children : [
{
name : '北京',
children : [
{
name : '朝阳群众'
},
{
name : '海淀区'
},
{
name : '昌平区'
}
]
},
{
name : '浙江省',
children : [
{
name : '杭州市',
code : 0571,
},
{
name : '嘉兴市'
},
{
name : '绍兴市'
},
{
name : '宁波市'
}
]
}
]
};
var node = dfs(tree, '杭州市');
console.log(node); // { name: '杭州市', code: 0571 }
这个对我来讲不容易。。倒是做出来,面试官也没说到这题有问题。
这是我的实现代码: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
28var dfs = function (treeNodes, name) {
if (!treeNodes || !treeNodes.children.length) {
return
}
var stack = [];
//先将第一层节点放入栈
for (var i = 0, len = treeNodes.children.length; i < len; i++) {
stack.push(treeNodes.children[i]);
}
var item;
while (stack.length !== 0) {
item = stack.shift();
if (item.name === name) {
var result = {
name: name,
code: item.code
}
return result
}
if (item.children && item.children.length !== 0) {
stack = item.children.concat(stack);
}
}
};
递归写法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17var parseTreeJson = function(tree){
var treeNodes = tree.children
if (!treeNodes || !treeNodes.length) {
return;
}
for (var i = 0, len = treeNodes.length; i < len; i++) {
var childs = treeNodes[i].children;
console.log(treeNodes[i].name);
if(childs && childs.length > 0){
parseTreeJson(childs);
}
}
};