前端笔试中两道与节点有关的算法题

1.分别用广度优先遍历和深度优先遍历展开下面节点
示例
var tree = {
name: ‘root’,
children: [{
name: ‘child1’,
children: [{
name: ‘child1_1’,
children: []
}, { name: ‘child1_2’, children: [] }]
}, {
name: ‘child2’,
children: [{
name: ‘child2_1’,
children: []
}]
}, {
name: ‘child3’,
children: [{
name: ‘child2_1’,
children: []
}]
}]
};
广度优先遍历：
function wideTraversal(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node);
while (queue.length != 0) {
var item = queue.shift();
nodes.push(item.name);
var children = item.children;
for (var i = 0; i < children.length; i++) {

queue.push(children[i]);
}
}

}
return nodes;
}
console.log(wideTraversal(tree))
输出结果：
[ ‘root’,’child1′,’child2′,’child3′,’child1_1′,’child1_2′,’child2_1′,’child2_1′ ]
深度优先遍历：
function traverseTree(node) {
var child = node.children,
arr = [];

arr.push(node.name);
if (child) {
child.forEach(function(node) {
arr = arr.concat(traverseTree(node));
});
}
return arr;
}
console.log(traverseTree(tree))
输出结果：
[ ‘root’,’child1′,’child1_1′,’child1_2′,’child2′,’child2_1′,’child3′,’child2_1′ ]
2.关系型数组转换成树形结构对象
类似：
var data = [
{ parentId: 0, id: 1, value: ‘1’ },
{ parentId: 3, id: 2, value: ‘2’ },
{ parentId: 0, id: 3, value: ‘3’ },
{ parentId: 1, id: 4, value: ‘4’ },
{ parentId: 1, id: 5, value: ‘5’ }
]
期望输出：
[
{id:1,value:’1′,
children:[{id:4,value:’4′,children:[]},
{id:5,value:’5′,children:[]}]},
{id:3,value:’3′,
children:[id:2,value:’2′,children:[]]}]
代码：
var getJsonTree = function(data, parentId) {
var itemArr = [];
for (var i = 0; i < data.length; i++) {
var node = data[i];
//data.splice(i, 1)
if (node.parentId == parentId) {
var newNode = { id: node.id, value: node.value, children: getJsonTree(data, node.id) };
itemArr.push(newNode);
}
}
return itemArr;
}
console.log(getJsonTree(data, 0))