列表转成树形结构 #41

Sunny-117 · 2022-11-03T07:26:44Z

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 · 2022-11-03T09:31:38Z

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 · 2022-11-03T10:50:28Z

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

pengyinghao · 2022-11-03T12:27:54Z

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 · 2022-12-19T01:42:43Z

 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 · 2022-12-21T12:33:41Z

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 · 2023-01-11T05:45:04Z

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 · 2023-01-12T09:38:37Z

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 · 2023-01-15T07:47:46Z

//时间复杂度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 · 2023-01-27T03:06:44Z

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 · 2023-01-31T06:45:57Z

 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 · 2023-02-14T03:01:53Z

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 · 2023-02-14T09:05:20Z

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 · 2023-02-23T03:48:46Z

时间复杂度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 · 2023-02-26T13:04:57Z

时间复杂度 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 · 2023-02-27T09:30:40Z

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 · 2023-03-03T18:08:41Z

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 · 2023-03-06T06:25:31Z

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 · 2023-03-13T00:58:07Z

    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 · 2023-03-16T08:20:48Z

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 · 2023-06-13T01:59:43Z

一种复杂度为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 · 2023-07-17T10:45:49Z

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 · 2023-08-17T08:37:51Z

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 · 2023-09-07T09:49:56Z

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 · 2024-01-24T01:29:14Z

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 · 2024-07-08T15:19:43Z

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 · 2024-09-15T08:27:17Z

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 · 2024-10-27T13:55:49Z

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)

Windseek · 2024-11-05T09:32:06Z

Windseek · 2024-11-05T12:36:28Z

`const listToTree = (list) => {
let tree = [];
let hashMap = {};
list.forEach(item => {
hashMap[item.pid] ? hashMap[item.pid].push(item) : hashMap[item.pid] = [item]
})
list.forEach(item => {
if(hashMap[item.id]) {
item.children = hashMap[item.id];
}
if(item.pid === 0) {
tree.push(item);
}
})
return tree;
}

console.log(listToTree(arr));`

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

列表转成树形结构 #41

列表转成树形结构 #41

Sunny-117 commented Nov 3, 2022

Jesslynwong commented Nov 3, 2022

Sunny-117 commented Nov 3, 2022

pengyinghao commented Nov 3, 2022 •

edited

Loading

xubaobao19940428 commented Dec 19, 2022

lmscc commented Dec 21, 2022 •

edited

Loading

fencer-yd commented Jan 11, 2023

ox4f5da2 commented Jan 12, 2023

veneno-o commented Jan 15, 2023 •

edited

Loading

coffeeAndTeaa commented Jan 27, 2023

ppjiucai commented Jan 31, 2023

sv-98-maxin commented Feb 14, 2023 •

edited

Loading

zzyyhh22lx commented Feb 14, 2023

kangkang123269 commented Feb 23, 2023

LifeIsTerrible commented Feb 26, 2023

bearki99 commented Feb 27, 2023

xudaotutou commented Mar 3, 2023

yanyunwu commented Mar 6, 2023 •

edited

Loading

xun-zi commented Mar 13, 2023

xuezechao2012 commented Mar 16, 2023 •

edited

Loading

GeorgeHcc commented Jun 13, 2023

shaliantao commented Jul 17, 2023

why-ztc commented Aug 17, 2023

Liboq commented Sep 7, 2023

spicylemonhaha commented Jan 24, 2024

stryear commented Jul 8, 2024

jianxingyao commented Sep 15, 2024

csdoge007 commented Oct 27, 2024

Windseek commented Nov 5, 2024

Windseek commented Nov 5, 2024

列表转成树形结构 #41

列表转成树形结构 #41

Comments

Sunny-117 commented Nov 3, 2022

Jesslynwong commented Nov 3, 2022

Sunny-117 commented Nov 3, 2022

pengyinghao commented Nov 3, 2022 • edited Loading

xubaobao19940428 commented Dec 19, 2022

lmscc commented Dec 21, 2022 • edited Loading

fencer-yd commented Jan 11, 2023

ox4f5da2 commented Jan 12, 2023

veneno-o commented Jan 15, 2023 • edited Loading

coffeeAndTeaa commented Jan 27, 2023

ppjiucai commented Jan 31, 2023

sv-98-maxin commented Feb 14, 2023 • edited Loading

zzyyhh22lx commented Feb 14, 2023

kangkang123269 commented Feb 23, 2023

LifeIsTerrible commented Feb 26, 2023

时间复杂度 O(n2)

bearki99 commented Feb 27, 2023

xudaotutou commented Mar 3, 2023

yanyunwu commented Mar 6, 2023 • edited Loading

xun-zi commented Mar 13, 2023

xuezechao2012 commented Mar 16, 2023 • edited Loading

GeorgeHcc commented Jun 13, 2023

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

shaliantao commented Jul 17, 2023

why-ztc commented Aug 17, 2023

Liboq commented Sep 7, 2023

spicylemonhaha commented Jan 24, 2024

stryear commented Jul 8, 2024

jianxingyao commented Sep 15, 2024

csdoge007 commented Oct 27, 2024

Windseek commented Nov 5, 2024

Windseek commented Nov 5, 2024

pengyinghao commented Nov 3, 2022 •

edited

Loading

lmscc commented Dec 21, 2022 •

edited

Loading

veneno-o commented Jan 15, 2023 •

edited

Loading

sv-98-maxin commented Feb 14, 2023 •

edited

Loading

yanyunwu commented Mar 6, 2023 •

edited

Loading

xuezechao2012 commented Mar 16, 2023 •

edited

Loading