折叠何宝莹

深度优先搜索算法(递归和非递归两种方法)

这个也是最近遇到的题目

深度优先搜索
实现一个深度优先搜索算法(非递归)

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
28
var 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
17
var 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);
}
}
};