Fe-interview: 第 29 题：手写数组转树

[lgwebdream]

欢迎在下方发表您的优质见解

[Genzhen]

let input = [
  {
    id: 1,
    val: "学校",
    parentId: null,
  },
  {
    id: 2,
    val: "班级1",
    parentId: 1,
  },
  {
    id: 3,
    val: "班级2",
    parentId: 1,
  },
  {
    id: 4,
    val: "学生1",
    parentId: 2,
  },
  {
    id: 5,
    val: "学生2",
    parentId: 3,
  },
  {
    id: 6,
    val: "学生3",
    parentId: 3,
  },
];
function buildTree(arr, parentId, childrenArray) {
  arr.forEach((item) => {
    if (item.parentId === parentId) {
      item.children = [];
      buildTree(arr, item.id, item.children);
      childrenArray.push(item);
    }
  });
}
function arrayToTree(input, parentId) {
  const array = [];
  buildTree(input, parentId, array);
  return array.length > 0 ? (array.length > 1 ? array : array[0]) : {};
}
const obj = arrayToTree(input, null);
console.log(obj);

[Genzhen]

例如
[{id:1, parentId: 0}, {id:2, parentId:1},{id:3, parentId:1}]
把这个数组从顶级分类递归查找子分类，最终构建一个树状数组。结果输出如下
[{id:1, parentId: 0,children:[{id:2, parentId:1},{id:3, parentId:1}]}]
parentId为0 的是根节点

代码实现

// 输入
const tempArr = [{
    id: 1,
    parentId: 0
  },
  {
    id: 2,
    parentId: 1
  },
  {
    id: 3,
    parentId: 1
  },
  {
    id: 4,
    parentId: 2
  },
];

function arrayToTree(sourceArr) {
  sourceArr.forEach(item => {
    let parentId = item.parentId;
    if (parentId !== 0) {
      sourceArr.forEach(subitem => {
        if (subitem.id == parentId) {
          if (!subitem.children) {
            subitem.children = [];
          }
          subitem.children.push(item);
        }
      });
    }
  });
  return sourceArr.filter(item => item.parentId === 0);
}
console.log(arrayToTree(tempArr));

[Genzhen]

数组转树的其中一种，排序数组转二叉搜索树

/**
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = null;
 *     this.right = null;
 * }
 */

var sortedArrayToBST = function (nums) {
    if (!nums.length) {
        return null
    };
    const root = new TreeNode(null);

    if (nums.length > 1) {
        root.left = sortedArrayToBST(nums.splice(0, nums.length / 2))
    };
    root.val = nums[0];
    root.right = sortedArrayToBST(nums.splice(1));
    return root;
};

[523451928]

var list = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 1 },
  { id: 5, name: '部门E', parentId: 2 },
  { id: 6, name: '部门F', parentId: 3 },
  { id: 7, name: '部门G', parentId: 2 },
  { id: 8, name: '部门H', parentId: 4 }
];
function convert(list) {
  const map = list.reduce((acc, item) => {
    acc[item.id] = item
    return acc
  }, {})
  const result = []
  for (const key in map) {
    const item = map[key]
    if (item.parentId === 0) {
      result.push(item)
    } else {
      const parent = map[item.parentId]
      if (parent) {
        parent.children = parent.children || []
        parent.children.push(item)
      }
    }
  }
  return result
}
var result = convert(list)

[fengmiaosen]

function convertStr(list) {
    const res = [];

    const map = new Map();

    for (let i = 0; i < list.length; i++) {
        map.set(list[i].id, list[i]);
    }

    for (let item of list) {
        if (item.parentId == null) {
            res.push(item);
        } else {
            const pItem = map.get(item.parentId);
            pItem.children = pItem.children || [];
            pItem.children.push(item);
        }
    }

    return res;
}

[GolderBrother]

function arrayToTree(array = []) {
    // 获取祖先节点
    const root = array.shift();
    const tree = {
        id: root.id,
        val: root.val,
        children: toTree(root.id, array)
    };
    return tree;
}

function toTree(parentId, array = []) {
    const children = [];
    for (let index = 0, len = array.length; index < len; index++) {
        const node = array[index];
        // 找到儿子节点
        if (node.parentId === parentId) {
            children.push({
                id: node.id,
                val: node.val,
                children: toTree(node.id, array)
            });
        }

    }
    return children;
}

[wang2498]

// 非递归版
const arrayToTree = (arr = []) => {
  let map = {};
  let tree = [];
  for (let i in arr) {
    map[arr[i].id] = arr[i];
  }
  for (let i in map) {
    if (map[i].parentId) {
      if (!map[map[i].parentId].children) {
        map[map[i].parentId].children = [];
      }
      if (map[map[i].parentId].children) {
        map[map[i].parentId].children.push(map[map[i].id]);
      }
    } else {
      tree.push(map[i]);
    }
  }
  return tree;
}

[xiaobei07]

function arrToTre(params) {
const result = params.map(item => {
if (!item.children) {
item.children = []
}
const parent = findParent(item,params)
parent && parent.children.push(item)
return item
})
return result[lowIndex(params)]
}
function findParent(obj,arr) {
let result = null
arr.map(item => {
if (item.id === obj.parentId) {
item.children ? '' : item.children = []
result = item
}
})
return result
}

function lowIndex(arr) {
let ind = Infinity
let id = Infinity
arr.map((item,index) => {
if (item.id < id){
id = item.id
ind=index
}
})
return ind
}
const result = arrToTre(input)

[v1nkon]

export const listToTree = (listData) => {
  let ids = [],
      objs = [];
  listData.map(item => {
      ids.push(item.id)
      objs.push({
          id:item.id,
          title: item.label,
          pid:item.pid,
          children: []
      })
  })
  let parents = []
  objs.map( cur => {  
      let index = ids.indexOf(cur.pid)
      if( index >=0 ){
          objs[index].children.push(cur)
      }else{
          parents.push({
              ...cur,
              isParent:true
          })
      }
  } )

  return parents
}

[NameWjp]

export function listToTree(soure, pid = 0) {
  const result = []
  let temp

  soure.forEach((e) => {
    if (e.parentId === pid) {
      temp = listToTree(soure, e.id)
      if (temp.length > 0) {
         e.children = temp
      }
      result.push(e)
    }
  })
  return result 
}

[myzhoulang]

let obj
for(let item of input){
  if(!item.parentId) obj = item
  const children = input.filter(it => it.parentId === item.id)
  if(children.length > 0) item.children = children
}

[xsfxtsxxr]

var list = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 1 },
  { id: 5, name: '部门E', parentId: 2 },
  { id: 6, name: '部门F', parentId: 3 },
  { id: 7, name: '部门G', parentId: 2 },
  { id: 8, name: '部门H', parentId: 4 }
];
function convert(list) {
  const map = list.reduce((acc, item) => {
    acc[item.id] = item
    return acc
  }, {})
  const result = []
  for (const key in map) {
    const item = map[key]
    if (item.parentId === 0) {
      result.push(item)
    } else {
      const parent = map[item.parentId]
      if (parent) {
        parent.children = parent.children || []
        parent.children.push(item)
      } else{
        result.push(item) // 要加上else，否则，5，7就被抛弃了
      }
    }
  }
  return result
}
var result = convert(list)

@523451928 要加上else，否则，5，7就被抛弃了

[lei1248276]

function transTree(arr) {
    let map = arr.reduce((acc, item) => {
      acc[item.id] = item;
      item.children = [];
      return acc
    }, {})
    for (const key in map) {
      if (map.hasOwnProperty(key)) {
        let node = map[key];
        if (map[node.parentId]) {
          map[node.parentId].children.push(node)
        }
        delete node.parentId;
      }
    }
    return map[1];
  }
  console.log(transTree(input));

[qzruncode]

考的就是你对对象引用熟不熟

function arrToObj(arr) {
  arr = Array.from(arr, (v, k) => Object.assign({}, v)); // 基于引用来的做的，这里的arr需要拷贝一下
  let root = [];
  arr.forEach(item => {
    if(item.parentId == 0) {
      root.push(item);
    }else {
      const parent = arr.find(iitem => iitem.id == item.parentId);
      parent.children ? parent.children.push(item) : parent.children = [item];
    }
  });
  return root;
}
const arr = [
  { id: 1, name: '部门A', parentId: 0 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 1 },
  { id: 5, name: '部门E', parentId: 0 },
  { id: 6, name: '部门F', parentId: 3 },
  { id: 7, name: '部门G', parentId: 0 },
  { id: 8, name: '部门H', parentId: 4 }
];
arrToObj(arr)

[HeMin0919]

function setTreeData(data) {
    let cloneData = JSON.parse(JSON.stringify(data))    // 对源数据深度克隆
    let tree = cloneData.filter((father) => {              //循环所有项
        let branchArr = cloneData.filter((child) => {
            return father.rankId == child.parentId      //返回每一项的子级数组
        });
        if (branchArr.length > 0) {
            father.children = branchArr;    // 如果存在子级，则给父级添加一个children属性，并赋值
        }
        return father.parentId == 0;      //返回第一层
    });
    return tree     //返回树形数据
}
let data = [
    {
        rankId: 1,
        value: 'BeiJing',
        label: '北京',
        parentId: 0,
    },
    {
        rankId: 2,
        value: 'jiangsu',
        label: '江苏',
        parentId: 0,
    },
    {
        rankId: 3,
        value: 'gugong',
        label: '故宫',
        parentId: 1,
    },
    {
        rankId: 4,
        value: 'tiantan',
        label: '天坛',
        parentId: 1,
    },
    {
        rankId: 5,
        value: 'zhengyangmen',
        label: '正阳门',
        parentId: 1,
    }
  ]
  console.log('setTreeData', setTreeData(data));

[laihaoshan]

打印了一下各位大佬的代码，就想问一下，你们是怎么确定childnren一定是放在那个位置的？

[DakerHub]

时间复杂度 O(n) 的操作，不考虑原数组修改

function toTree(arr) {
  var idMap = {}
  arr.forEach((n) => {
    idMap[n.id] = n
  })

  for (let i = 0; i < arr.length; i++) {
    const node = arr[i]
    const parentNode = idMap[node.parentId]
    if (parentNode) {
      if (Array.isArray(parentNode.children)) {
        parentNode.children.push(node)
      } else {
        parentNode.children = [node]
      }
    }
  }

  return arr.filter((n) => n.parentId === 0)
}