преобразовать массив

Массив
[ {"name":"root", "parentId":null, "id":100}, {"name":"1stlevelChild1", "parentId":100, "id":201}, {"name":"1stlevelChild2", "parentId":100, "id":202}, {"name":"2ndlevelChild1", "parentId":201, "id":301}, {"name":"2ndlevelChild2", "parentId":201, "id":301} ]
Преобразовать в иерархический
[ { "name":"root", "parentId":null, "id":100, "childs":[ { "name":"1stlevelChild1", "parentId":100, "id":201, "childs":[ {"name":"2ndlevelChild1", "parentId":201, "id":301, "childs":[]}, {"name":"2ndlevelChild2", "parentId":201, "id":301, "childs":[]} ] }, { "name":"1stlevelChild2", "parentId":100, "id":202, "childs":[] } ] } ]
Какими способами это можно сделать, какие функции использовать?

Ответ

var input = [ {"name":"root", "parentId":null, "id":100}, {"name":"1stlevelChild1", "parentId":100, "id":201}, {"name":"1stlevelChild2", "parentId":100, "id":202}, {"name":"2ndlevelChild1", "parentId":201, "id":301}, {"name":"2ndlevelChild2", "parentId":201, "id":302} ]; var output = []; var lookup = {}; // prepare lookup container and arrays for children for (var i = 0; i < input.length; i++) { input[i].children = []; lookup[input[i].id] = input[i]; } // distribute items from input to output and their parents for (var i = 0; i < input.length; i++) { if (input[i].parentId == null) output.push(input[i]); else lookup[input[i].parentId].children.push(input[i]); } console.log(output);
Объекты во входном массиве не имеют массивов для детей, создаем их в цикле в каждом объекте: input[i].children = [];. Чтобы быстро находить родителя по его id, используем bracket notation обращения к свойствам js объектов, а в качестве названий свойств - значения id элементов массива: lookup[input[i].id] = input[i];. Когда нам понадобится быстро найти родительский объект, мы найдем его в lookup, как свойство lookup[input[i].parentId]