一道js递归算法题

Question

1.有树状结构的一个对象数组
[{id:0},
{id:1,parentId:0},
{id:2},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}]

2.要求排完顺序为
[{id:0},
{id:1,parentId:0},
{id:3,parentId:1},
{id:5,parentId:3}
{id:4,parentId:0},
{id:2}]
解释一下：就是一个深度优先遍历吧，有父节点的数据会有parentId这个属性，如果一个节点有子节点（有节点parentID==它自己的id），则直接插入他的子节点，循环直到插入节点没有子节点为止。同级的按照之前的先后顺序排列。

思路大概有，但是写了半天都是错的，求大神给个demo学习一下

Answer 1

https://jsfiddle.net/g7askt9w... 只能先写个这个样的 开销很大如果数据很大

let datas =[{id:0},{id:2},
{id:1,parentId:0},
{id:6,parentId:2},
{id:7,parentId:6},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}]
let arr=[]
function treedata(data,a){
   data.forEach((r,index)=>{
      if(r.parentId==a.id){
        arr.push(r)
        /* datas.splice(index,1) */
        treedata(datas,r)
      }
       
   })
}
datas.forEach((r,index)=>{
   if(r.parentId || r.parentId===0){
   }else{
      arr.push(r)
      /* datas.splice(index,1) */
      treedata(datas,r) 
   }
})
console.log(arr) 

Answer 2

var array =[{id:0},
{id:1,parentId:0},
{id:2},
{id:3,parentId:1},
{id:4,parentId:0},
{id:5,parentId:3}];

//构造树结构
for(var i = 0;i < array.length;i++){
      var cur = array[i];
        for(var j = i+1;j < array.length;j++){
            var next = array[j];
            if(cur.id === next.parentId){
                     if(!cur.nextIndexArray){
                                cur.nextIndexArray = [];
                         }
                      cur.nextIndexArray.push(j);
                    next.preIndex = i;
            }else if(cur.parentId === next.id){
                    if(!next.nextIndexArray){
                                next.nextIndexArray = [];
                         }
                      next.nextIndexArray.push(i);
                    cur.preIndex = j;
            }
        }
}
var result = [];
//递归遍历树结构
function recursiveTree(obj){
     result.push(obj);
      var nextIndexArray = obj.nextIndexArray;
      if(!nextIndexArray){
            return;
        }
      for(var i = 0;i < nextIndexArray.length;i++){
               recursiveTree(array[nextIndexArray[i]]);
        }
}
for (var i = 0;i < array.length;i++){
       if(typeof(array[i].preIndex) == "undefined"){
                recursiveTree(array[i]);
         }
}
console.log(result);