Open dave-wind opened 1 year ago
首先介绍 DFS 深度优先搜索
DFS(深度优先搜索)算法,用于找到从起点到目标节点的最短路径。 ,* 给定一个起始节点,
这将返回树中具有目标值的起始节点下方的节点(如果不存在,则返回 null) ,
* 在 O(n) 中运行,其中 n 是树中的节点数,或 O(b^d),其中 b 是分支因子,d 是深度。
const dfs = function (start, target) {
console.log("Visiting Node " + start.value);
if (start.value === target) {
// We have found the goal node we we're searching for
console.log("Found the node we're looking for!");
return start;
}
// Recurse with all children
for (var i = 0; i < start.children.length; i++) {
var result = dfs(start.children[i], target);
if (result != null) {
// We've found the goal node while going down that child
return result;
}
}
// We've gone through all children and not found the goal node
console.log("Went through all children of " + start.value + ", returning to it's parent.");
return null;
};
解: 性能很差 因为每次都要找到底部;
// 根据DFS原理 就好比俩点找最短路径, 都是一条路走到底不行再换下一条;
// 所以判断子元素parentId == 目标id的时候 就一直递归下去;直到不等于;但是 性能不好 不是 O(n)
function convert(source, parentId = 0){
let trees = [];
for (let item of source) {
// 递归条件 也是基线条件 当不满足就直接 不会递归了
if(item.parentId === parentId) {
let children = convert(source, item['id']);
if(children.length) {
item.children = children
}
trees.push(item);
}
}
return trees;
}
递归法: O(n^2)
function convert(arr, result = []) {
for (let index = 0; index < arr.length; index++) {
// 当前每一个对象
let current = arr[index]
if (current.parentId == 0) { // 为0 直接push
result.push(current);
} else {
const findParent = arr.find(item => current.parentId == item.id); // 去找父级
if (findParent) {
findParent.children = findParent.children || [];
findParent.children.push(current);
// 第一次循环结束 继续下一次循环
convert2(findParent.children, result)
}
}
}
return result;
}
最佳解法: O(n) + O(n) ~= O(n)
function createMap(arr) {
let obj = {}
arr.forEach((item) => {
obj[item.id] = item; // 注意这里 不能用 对象解构 扩展符 因为就是为了 引用指向同一个
obj[item.id].children = []
})
return obj
}
function createTree(arr, map) {
let result = []
arr.forEach((item) => {
// 为0 做根元素
if (item.parentId == 0) {
result.push(item);
} else {
// 通过 parentid 去找 父 id; 这里利用的就是引用一样; 无论多深层级 都可以找到向上的父级
const findParent = map[item.parentId];
if (findParent) {
findParent.children.push(item)
}
}
})
return result;
}
function convert(arr) {
const map = createMap(arr);
return createTree(arr, map)
}
1.1. 题干
完成下列树的结构定义
1.2. 问题
完成以下数据结构定义
class Tree {
add(…nodes) {
// todo
// 添加节点。可多次添加
}
json() {
// todo
// 将整棵树转换成json字符串
}
getNodeTotalRank(id) {
// todo
// 获取节点及其后代节点的rank合计
// 25
}
getNodeAncestorIds(id) {
// todo
// 获取节点的所有祖先节点的编号,并以节点层次为顺序
// [1, 2, 3]
}
}
解:
class Tree {
constructor() {
this.root = []
this.map = new Map();
}
setMap(target) {
for (let i = 0; i < target.length; i++) {
const itm = target[i];
if (!this.map.has(itm.id)) {
itm.children = [];
this.map.set(itm.id, itm);
}
}
}
transform(arr) {
for (let i = 0; i < arr.length; i++) {
const itm = arr[i];
if (!itm.parentId) {
this.root.push(itm);
} else {
let findParent = this.map.get(itm.parentId)
if (findParent) {
findParent.children.push(itm);
}
}
}
return this.root;
}
add(nodes) {
this.setMap(nodes);
const arr = this.transform(nodes);
return arr[0];
}
deepjson(target) {
let result = Array.isArray(target) ? [] : {};
if (target && typeof target === 'object' && target !== null) {
for (let key in target) {
const itm = target[key];
if (target.hasOwnProperty(key)) {
if (Array.isArray(itm)) {
result[key] = this.deepjson(itm);
} else {
result[key] = itm;
}
}
}
}
return result;
}
json() {
return this.deepjson(this.root[0])
}
getNodeById(source, id) {
var result, isOver = false;
function handlefn(source) {
if (Array.isArray(source) && !isOver) {
for (let i = 0; i < source.length; i++) {
const itm = source[i];
if (itm.id == id) {
result = itm;
isOver = true;
} else {
handlefn(itm.children)
}
}
}
}
handlefn(source);
return result;
}
reduceNumByKey(arr, key) {
let rank = 0;
for (let i = 0; i < arr.length; i++) {
const itm = arr[i];
rank += itm[key];
if (Array.isArray(itm.children)) {
rank += this.reduceNumByKey(itm.children, key)
}
}
return rank
}
getNodeTotalRank(id) {
const getNode = this.getNodeById(this.root, id);
return this.reduceNumByKey([getNode], 'rank')
}
getNodeAncestorIds(id) {
let arr = [], obj = this.map;
function excuteFn(id) {
const find = obj.get(id)
if (find && find.id) {
if (find.parentId !== null) {
arr.push(find.parentId);
excuteFn(find.parentId)
}
}
}
excuteFn(id);
return arr.sort((a, b) => a - b);
}
}
// 参数:
const nodes1 = [
{ id: 1, parentId: null, label: "4", rank: 1 },
{ id: 2, parentId: 1, label: "4", rank: 3 },
{ id: 3, parentId: 2, label: "22", rank: 2 },
{ id: 4, parentId: 3, label: "3q", rank: 7 },
{ id: 7, parentId: 2, label: "83", rank: 8 },
{ id: 8, parentId: 6, label: "d6", rank: 5 },
{ id: 9, parentId: 6, label: "b2", rank: 4 },
{ id: 10, parentId: 3, label: "1k", rank: 3 },
{ id: 11, parentId: 3, label: "133", rank: 9 },
{ id: 12, parentId: 3, label: "kg", rank: 9 },
{ id: 13, parentId: 1, label: "160", rank: 0 },
{ id: 14, parentId: 12, label: "1mf", rank: 2 },
{ id: 15, parentId: 7, label: "h8", rank: 0 },
{ id: 16, parentId: 13, label: "oh", rank: 0 },
{ id: 17, parentId: 3, label: "1a1", rank: 8 },
{ id: 5, parentId: 3, label: "e", rank: 2 },
{ id: 6, parentId: 4, label: "3r", rank: 9 },
];
const nodes2 = [
{ id: 18, parentId: 6, label: "13f", rank: 0 },
{ id: 20, parentId: 3, label: "189", rank: 8 },
{ id: 19, parentId: 17, label: "1i2", rank: 5 },
];
var tree = new Tree();
// 调用方式 参数无需展开
tree.add(nodes1);
console.log('totalRank---', tree.getNodeTotalRank(4)); // 25
tree.add(nodes2);
console.log('json---', tree.json()); // 相当于 deepclone
console.log('rank2---', tree.getNodeTotalRank(3)); // 73
console.log('AncestorIds----', tree.getNodeAncestorIds(4)); // [1,2,3]
数组转tree