列表转成树形结构

[Sunny-117]

let arr = [
    { id: 1, name: '部门1', pid: 0 },
    { id: 2, name: '部门2', pid: 1 },
    { id: 3, name: '部门3', pid: 1 },
    { id: 4, name: '部门4', pid: 3 },
    { id: 5, name: '部门5', pid: 4 },
    { id: 6, name: '部门6', pid: 0 },
]
function getTreeList(rootList, id, list) {
    for (const item of rootList) {
        if (item.parent === id) {
            list.push(item);
        }
    }
    for (const i of list) {
        i.children = [];
        getTreeList(rootList, i.id, i.children);
        if (i.children.length === 0) {
            delete i.children;
        }
    }
    return list;
}
const res = getTreeList(rootList, null, []);
console.log("res", res);

[Jesslynwong]

function get_tree(arr) {
  const list = []

  arr.forEach(element => {
    const chiildren_arr = arr.filter(ele => {
      return element.id === ele.pid
    })

    if (chiildren_arr.length > 0) {
      element.chiildren = chiildren_arr
    }

    if (element.pid === 0) {
      list.push(element)
    }
  });

  return list
}
console.log(get_tree(arr));

以上时间复杂度是On^2 下面做法利用引用能够达到On

function get_tree(arr) {
  const list = [];
  const hashmap = {};

  for (let i = 0; i < arr.length; i++) {
    // 存储每个id下的子元素
    let pid = arr[i].pid
    let id = arr[i].id

      if (!hashmap[id]) {
        hashmap[id] = {children:[]}
      }

      hashmap[id] = {...arr[i], children:hashmap[id].children}

    if (pid === 0) {
      list.push(hashmap[id]);
    } else {
     if (!hashmap[pid]) {
       hashmap[pid] = {
         children:[]
       }
     }

     hashmap[pid].children.push(hashmap[id])
    }
  }
  return list;
}

const ans = get_tree(arr)
console.log(ans)

[Sunny-117]

大佬的解法nb，看来讨论的效果出现了哈哈

[pengyinghao]

const generateTree = (data) => {
  if (!data || data.length === 0) return [];
  const obj = {};
  data.forEach((item) => {
    const { pid } = item;
    if (!obj[pid]) {
      obj[pid] = [];
    }
    obj[pid].push(item);
  });
  data.forEach((item) => {
    item.children = obj[item.id] || [];
  });
  const result = data.filter((item) => item.pid === 0);
  console.log(result);
  return result;
};
const result = generateTree(arr);
console.log(result);

[xubaobao19940428]

 function arrayToTree(arr) {
 let result = []
 if(!Array.isArray(arr) || arr.length === 0) {
      return result
}
let map = {}
arr.forEach((item) => (map[item.id] = item))
arr.map((item) => {
const parent = map[item.pid]
if (parent != undefined) {
parent.children || (parent.children = []).push(item)
} else {
result.push(item)
}
})
return result
},

[lmscc]

let arr = [
    { id: 1, name: '部门1', pid: 0 },
    { id: 2, name: '部门2', pid: 1 },
    { id: 3, name: '部门3', pid: 1 },
    { id: 4, name: '部门4', pid: 3 },
    { id: 5, name: '部门5', pid: 4 },
    { id: 6, name: '部门6', pid: 0 },
]

function list2tree(arr) {
    let map = {}
    let newArr = []
    //先根据pid排个序,,这是个树形结构,pid越小说明越上层,
    arr.sort((a,b)=>a.pid-b.pid)
    for(let obj of arr){
        map[obj.id] = obj 
        if(obj.pid === 0){
            newArr.push(obj)
        }else{
            if(map[obj.pid].children){
                map[obj.pid].children.push(obj)
            }else{
                map[obj.pid].children = [obj]
            }

        }
    }
    return newArr
}
list2tree(arr)

[fencer-yd]

const data2 = [
  { id: '1', name: '父节点1', parentId: undefined },
  { id: '1-1', name: '子节点1-1', parentId: '1' },
  { id: '1-1-1', name: '子节点1-1-1', parentId: '1-1' },
  { id: '1-1-2', name: '子节点1-1-2', parentId: '1-1' },
  { id: '2', name: '父节点2', parentId: undefined },
  { id: '2-1', name: '子节点2-1', parentId: '2' }
];
function deepClone(value) {
  if (typeof value === 'object' && value !== null) {
    const result = Array.isArray(value) ? [] : {};
    for (const key in value) {
      result[key] = deepClone(value[key])
    }
    return result
  }
  return value
}
const result = deepClone(data2).reduce(function (acc, cur, idx, arr) {
  // 检索当前元素的子元素; tips: 此时操作cur会改变arr本身
  cur.cildren = arr.filter(item => item.parentId === cur.id);
  // 判断是否为根元素
  return arr.filter(item => !item.parentId)
}, []);

[ox4f5da2]

let arr = [
  { id: 1, name: '部门1', pid: undefined }, // 如果没有父元素则为undefined
  { id: 4, name: '部门4', pid: 3 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 5, name: '部门5', pid: 4 },
  { id: 6, name: '部门6', pid: undefined },
  { id: 3, name: '部门3', pid: 1 },
  { id: 7, name: '部门7', pid: 2 },
];

function list2tree(arr) {
  return arr.reduce((pre, { id, name, pid }) => {
    const children = pre.get(id) ?? [];
    const parent = pre.get(pid) ?? [];
    parent.push({ id, name, children });
    return pre.set(id, children).set(pid, parent);
  }, new Map()).get(undefined);
}

console.dir(list2tree(arr));

[veneno-o]

//时间复杂度O(2n) 空间复杂度O(n)
function format(arr) {
    const map = new Map();

    for (let i = 0; i < arr.length; ++i) {
        const pid = arr[i].pid;
        map.has(pid) ? map.get(pid).push(i) : map.set(pid, [i]);
    }

       for(let i = 0; i < arr.length; ++i){
            delete arr[i].pid;
            const id = arr[i].id;
            map.has(id) && (arr[i].childre = map.get(id).map(i => arr[i]));
    }

    return map.get(0).map(i => arr[i]);
}

[coffeeAndTeaa]

function list2tree(arr) {
  const getChildren = (id, arr) => {
    let children = [];
    for (const node of arr) {
      // node is child
      if (node.pid === id) {
        children.push(node);
        let nodeChildren = getChildren(node.id, arr);
        if (nodeChildren.length !== 0) {
          node.children = nodeChildren;
        }
      }
    }
    return children;
  };
  const tree = [];
  arr.forEach((node) => {
    if (node.pid === 0 || arr.find((e) => e.id === node.pid) === undefined) {
      let childs = getChildren(node.id, arr);
      let newNode = { ...node };
      if (childs.length > 0) {
        newNode.children = childs;
      }
      tree.push(newNode);
    }
  });
  return tree;
}

[ppjiucai]

 function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }

    const treeItem =  itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }

  }
  return result;
}

[sv-98-maxin]

let arr = [
  { id: '1', name: '父节点1', pid: undefined },
  { id: '1-1', name: '子节点1-1', pid: '1' },
  { id: '1-1-1', name: '子节点1-1-1', pid: '1-1' },
  { id: '1-1-2', name: '子节点1-1-2', pid: '1-1' },
  { id: '2', name: '父节点2', pid: undefined },
  { id: '2-1', name: '子节点2-1', pid: '2' }
];

function listToTree(arr) {
  const res = [], map = new Map();
  // 创建hashMap，用pid当做键值
  for (let i of arr) {
    if (map.get(i.pid)) {
      map.get(i.pid).push(i)
    } else {
      map.set(i.pid, [i])
    }
  }
  arr.forEach(item => {
    if (map.get(item.id)) {
      item.children = map.get(item.id)
    }
    // 不是根节点就不用往里插了
    if (!item.pid) {
      res.push(item)
    }
  })
  return res
}

//解法2：
function listToTree(list) {
  const result = []
  list.forEach(node => {
    if (!node.pid) {
      result.push(node)
    } else {
      const parent = list.find(item => item.id === node.pid)
      if (list.find(item => item.id === node.pid)) {
        if (parent.children) {
          parent.children.push(node)
        } else {
          parent.children = [node]
        }
      }
    }
  })
  return result
}

[zzyyhh22lx]

O(n)复杂度实现

function transform(arr) {
    arr.sort((a, b) => a.id - b.id); // 对原数组id值进行升序排序
    const result = [];
    let hashMap = new Map();
    for (let i = 0; i < arr.length; i++) {
        let id = arr[i].pid;
        if(!hashMap.has(id)) result.push(arr[i]);
        else {
            let obj = hashMap.get(id);
            if(!obj.children) obj.children = []; // 动态添加children元素，也可以用# Object.defineProperty()
            obj.children.push(arr[i]);
        }
        hashMap.set(arr[i].id, arr[i]);
    }
    return result;
}

[kangkang123269]

时间复杂度O(n)

function listToTree(list) {
  const map = {};
  const roots = [];
  for (const item of list) {
    const id = item.id;
    const parent_id = item.parent_id;
    map[id] = { ...item, children: [] };
    if (parent_id === null) {
      roots.push(map[id]);
    } else {
      map[parent_id].children.push(map[id]);
    }
  }
  return roots;
}

[LifeIsTerrible]

时间复杂度 O(n2)

function jsonToTree(data) {
    let result = [];
    if (!Array.isArray(data)) return

    // 保存父级pid 0：没有父级 其他：存在父级
    let mapParent = {}
    // data.forEach(item => {
    //     mapParent[item.id] = item;
    // })
    // data.forEach(item => {
    //     // 判断是否存在父级
    //     let parent = mapParent[item.pid];
    //     if (parent) {
    //         (parent.children || (parent.children = [])).push(item)
    //     } else {
    //         result.push(item);
    //     }
    // })
    data.forEach(item => {
        const children_arr = data.filter(ele => {
            return ele.pid = item.id
        })
        if (children_arr.length) {
            item.children = children_arr;
        }
        if (item.pid === 0) {
            result.push(item);
        }
    })
    return result
}

[bearki99]

let arr = [
  { id: 1, name: "部门1", pid: 0 },
  { id: 2, name: "部门2", pid: 1 },
  { id: 3, name: "部门3", pid: 1 },
  { id: 4, name: "部门4", pid: 3 },
  { id: 5, name: "部门5", pid: 4 },
  { id: 6, name: "部门6", pid: 0 },
];
arr.sort((a, b) => a.pid - b.pid);
function list_to_tree(arr) {
  let map = {};
  const res = [];
  arr.forEach((item) => {
    map[item.id] = item;
    if (item.pid == 0) {
      res.push(map[item.id]);
    } else {
      if (map[item.pid].children) {
        map[item.pid].children.push(item);
      } else {
        map[item.pid].children = [item];
      }
    }
  });
  return res;
}
console.log(list_to_tree(arr));

[xudaotutou]

const list2tree = (list: Node[]): Node => list.reduce<[Node | null, Map<number, Node[]>]>(([_, children], v) => {
  const pid = v.pid
  const id = v.id
// 获取引用
  let ch = children.get(pid)
  if (ch) ch.push(v)
  else ch = []
  children.set(pid, ch)
// 获取引用
  let now = children.get(id)
  if (!Array.isArray(now)) {
    now = []
    children.set(id, now)
  }
  v.children = now

  if (pid === 0) return [v, children]
  else return [null, children]
}, [null, new Map<number, Node[]>()])[0]!

[yanyunwu]

O1

let arr = [
  { id: 1, name: '部门1', pid: 0 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 3, name: '部门3', pid: 1 },
  { id: 4, name: '部门4', pid: 3 },
  { id: 5, name: '部门5', pid: 4 },
  { id: 6, name: '部门6', pid: 0 },
]

const getTree = (list) => {
  const root = { pid: 0, children: [] }
  const map = new Map()
  map.set(0, root)

  const _getTree = (pid) => {

    if (pid === 0) {
      return root
    }

    if (!map.get(pid)) {
      map.set(pid, {})
    }

    const parent = map.get(pid)

    if (!parent.children) {
      parent.children = []
    }

    return parent
  }

  const _getItem = (item) => {
    const id = item.id

    if (!map.get(id)) {
      map.set(id, { ...item })
    } 

    return map.get(id)
  }

  for (let item of list) {
    const parent = _getTree(item.pid)
    parent.children.push(_getItem(item))
  }

  return root
}

console.log((getTree(arr)));

[xun-zi]

    let arr = [
        { id: 1, name: '部门1', pid: 0 },
        { id: 2, name: '部门2', pid: 1 },
        { id: 3, name: '部门3', pid: 1 },
        { id: 4, name: '部门4', pid: 3 },
        { id: 5, name: '部门5', pid: 4 },
        { id: 6, name: '部门6', pid: 0 },
    ]
    function ListTree(arr) {
        let root = null;
        const map = new Map();
        arr.forEach((item) => {
            item.children = [];
            map.set(item.id, item);
        })
        arr.forEach((item) => {
            const p = map.get(item.pid);
            if (!p) root = item;
            p?.children.push(item);
        })
        return root;
    }

    const treeNode = ListTree(arr)
    console.log('treeNode', treeNode)

[xuezechao2012]

function buildTree(arr, pid) {
  let result = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i].pid === pid) {
      let children = buildTree(arr, arr[i].id);
      if (children.length > 0) {
        arr[i].children = children;
      }
      result.push(arr[i]);
    }
  }

  return result;
}

let tree = buildTree(arr, 0);

chatGPT给的解法

[GeorgeHcc]

一种复杂度为O(n)的简单做法

const listToTree = (list) => {
  const hashMap = new Map();
  list.forEach((item) => {
    hashMap.set(item.id, item);
  });//list存入hash表
  list.forEach((item) => {
    if (hashMap.has(item.pid)) {
      const parent = hashMap.get(item.pid);
      if (parent.hasOwnProperty("children")) {
        parent.children.push(item);
      } else {
        parent.children = [item];
      }
    }
  });
  return [...hashMap.values()].filter((item) => item.pid === 0);//过滤出根节点
};

[shaliantao]

function list2Tree(arr) {
  const root = []
  const map = new Map(arr.map(item => [item.id, item]))
  for (const item of arr) {
    const parent = map.get(item.pid)
    if (parent) {
      parent.children ??= []
      parent.children.push(item)
    } else if(item.pid === 0) {
      root.push(item)
    } else {
      console.error(`节点:${item.id} ${item.name}没有父节点，请检查数据正确性`);
    }
  }
  return root
}

[why-ztc]

const list2tree = (list, rootId = 0) => {
  const map = {}
  const res = []
  list.forEach((item) => {
    map[item.id] = item
  })
  list.forEach((item) => {
    if (item.pid === rootId) {
      res.push(map[item.id])
    } else {
      map[item.pid].children ? map[item.pid].children.push(item) : map[item.pid].children = [item]
    }
  })
  return res
}

[Liboq]

const listToTree = (rootList, id = 0, list = []) => {
  for (const item in rootList) {
    if (rootList[item].pid === id) {
      list.push(rootList[item]);
      rootList.splice(item, 1);
    }
  }
  for (const i of list) {
    i.children = [];

    const children = rootList.filter((item) => {
      return item.pid === i.id;
    });
    children.forEach((item) => {
      item.children = [];
      const list1 = listToTree(rootList, item.id, list.children);
      item.children.push(...list1);
    });
    i.children.push(...children);
  }
  return list;
};

[spicylemonhaha]

O(n)复杂度实现

function transform(arr) {
    arr.sort((a, b) => a.id - b.id); // 对原数组id值进行升序排序
    const result = [];
    let hashMap = new Map();
    for (let i = 0; i < arr.length; i++) {
        let id = arr[i].pid;
        if(!hashMap.has(id)) result.push(arr[i]);
        else {
            let obj = hashMap.get(id);
            if(!obj.children) obj.children = []; // 动态添加children元素，也可以用# Object.defineProperty()
            obj.children.push(arr[i]);
        }
        hashMap.set(arr[i].id, arr[i]);
    }
    return result;
}

似乎用sort函数的时候复杂度就达到了nlogn

[stryear]

let list = [
    { id: 1, name: '部门1', pid: 0 },
    { id: 2, name: '部门2', pid: 1 },
    { id: 3, name: '部门3', pid: 1 },
    { id: 4, name: '部门4', pid: 3 },
    { id: 5, name: '部门5', pid: 4 },
    { id: 6, name: '部门6', pid: 0 },
]

function listToTree(list) {
    const map = {}; // 用于id到节点的映射
    const roots = []; // 存储根节点

    list.forEach(item => {
        map[item.id] = { ...item, children: [] }; // 初始化映射和children数组
    });

    list.forEach(item => {
        if (item.pid === 0) { // 如果有父节点
            roots.push(map[item.id]);
        } else { // 没有父节点，是根节点
            if (map[item.pid]) {
                map[item.pid].children.push(map[item.id]);
            }
        }
    });

    return roots;
}

[jianxingyao]

let arr = [
    { id: 1, name: '部门1', pid: 0 },
    { id: 2, name: '部门2', pid: 1 },
    { id: 3, name: '部门3', pid: 1 },
    { id: 4, name: '部门4', pid: 3 },
    { id: 5, name: '部门5', pid: 4 },
    { id: 6, name: '部门6', pid: 0 },
]

function listTransfromTree(arr) {
    const result = [];
    for (const item of arr) {
        if(item.pid === 0){
            result.push(item)
        }
        else{
            const parent = result.find(p => p.id === item.pid)
            if(parent){
                let children = parent.children
                if(!children){
                    children = parent.children = []
                }
                children.push(item)
            }
        }
    }

    return result
}
listTransfromTree(arr)

[csdoge007]

let list = [
  { id: 1, name: '部门1', pid: 0 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 3, name: '部门3', pid: 1 },
  { id: 4, name: '部门4', pid: 3 },
  { id: 5, name: '部门5', pid: 4 },
  { id: 6, name: '部门6', pid: 0 },
  { id: 0, name: '部门0' }
]

/**
 * 返回一个数组，表示root.children
 * @param {array} rootList 
 * @param {string} id 
 * @param {array} list 
 * @return {array}
 */
function getTreeList(rootList, id, list) {
  for (const item of rootList) {
    if (item.pid === id) {
      list.push(item)
    }
  }
  for (const item of list) {
    item.children = []
    getTreeList(rootList, item.id, item.children)
    if (item.children.length === 0) {
      delete item.children
    }
  }
  return list
}

/**
 * 返回树形结构
 * @param {Array<Object>} rootList
 * @return {Object}
 */
function getTreeData(rootList) {
  const root = rootList.find((item) => !item.hasOwnProperty('pid'))
  const rootChildren = getTreeList(rootList, root.id, [])
  return {
    ...root,
    children: rootChildren
  }
}

let treeData = getTreeData(list)