来个 js 算法大牛看看这个,有没有优雅点的代码?

Question

继上一题的一个反向算法
https://segmentfault.com/q/10...
源数据

[
  "浙江,宁波,鄞州区",
  "浙江,宁波,江北区",
  "浙江,杭州,富阳",
  "浙江,杭州,上城区",
  "上海,黄浦区"
]

目标结构

const data = [
  {
    city:'浙江',
    children:[
      {
        city:'宁波',
        children:[{
          city:'鄞州区',
          children:[]
        },{
          city:'江北区',
          children:[]
        }]
      },
      {
        city:'杭州',
        children:[{
          city:'富阳',
          children:[]
        },{
          city:'上城区',
          children:[]
        }]
      }
    ]
  },
  {
    city:'上海',
    children:[
      {
        city:'黄浦区',
        children:[]
      }
    ]
  }
]

Answer 1

这次不需要递归，只需要两层循环。

先来一个一般思路的解法：

const root = { children: [] };
const map = {};
data.forEach(item => {
    item.split(",").forEach((city, index, arr) => {
        const path = arr.slice(0, index + 1).join(",");
        const parentKey = arr.slice(0, index).join(",");
        const parent = map[parentKey] ?? root;
        parent.children.push(
            map[path] = {
                city,
                children: []
            }
        );
    });
});

这里 map 是建立一个路径（Key）到对象的映射，方便直接找到节点，在其下添加子节点。这里的 root 为了和节点结构一样，不是给的多根数组，直接给的节点模形。

不过这个解法里，拼 path 和 parentKey 有点繁琐。如果不用 map，而是每出现一个 Key 就直接按顺序去当前节点中找指定 Key 的节点，或者（如果不存在时）创建此节点的话，就会简化不少了，毕竟拆分字符串之后的 Key 都是有顺序的，不同于一般按路径查找节点的情况。

---

修改过后：

const roots = [];
data.forEach(item => {
    let parent = roots;
    item.split(",").forEach(city => parent = (
        parent.find(it => it.city === city)
        ?? parent[parent.push({ city, children: [] }) - 1]
    ).children);
});

当前父节点 parent 其实不是一个父节点，而是引用的父节点的 children，毕竟都是对 children 进行操作。

改过后的这段代码，主要逻辑在第二个 forEach() 中，就是在 parent 里查找指定 city 的节点，如果没找到就创建一个加进去。Array.prototype.push 返回新数组的长度，所以它的返回值 - 1 就是新添加的节点的索引。

---

改成这样了，再稍微改一下，用 reduce 就是一句话了

const roots = data.reduce((roots, item) => {
    item.split(",").reduce((parent, city) => (
        parent.find(it => it.city === city)
        ?? parent[parent.push({ city, children: [] }) - 1]
    ).children, roots);
    return roots;
}, []);

或者重新给代码排个版（仅改变了排版），下面这个是我比较喜欢的风格，层次结构比较清楚

const roots = data.reduce((roots, item) => {
    item.split(",").reduce(
        (parent, city) => (
            parent.find(it => it.city === city)
            ?? parent[parent.push({ city, children: [] }) - 1]
        ).children,
        roots
    );
    return roots;
}, []);

Answer 2

不过需要转换两次


let arr  = [
  "浙江,宁波,鄞州区",
  "浙江,宁波,江北区",
  "浙江,杭州,富阳",
  "浙江,杭州,上城区",
  "上海,黄浦区"
];

let relMap = arr.reduce((acc,cur)=>{
    let temp = acc;
    cur.split(',').forEach(item=>{
        temp = temp[item] = Object.assign({}, temp[item]);
    })
    return acc;
},{});
console.log(relMap);
let treeRel=(val)=>Object.entries(val).map(([key,val])=>({city:key, children:treeRel(val)}));
treeRel(relMap);

反向转换

data = [
  {
    city:'浙江',
    children:[
      {
        city:'宁波',
        children:[{
          city:'鄞州区',
          children:[]
        },{
          city:'江北区',
          children:[]
        }]
      },
      {
        city:'杭州',
        children:[{
          city:'富阳',
          children:[]
        },{
          city:'上城区',
          children:[]
        }]
      }
    ]
  },
  {
    city:'上海',
    children:[
      {
        city:'黄浦区',
        children:[]
      }
    ]
  }
]
let treeFlat = (data,level=0,path=[], res=[])=>{
    data.forEach(item=>{
        path.splice(level), // 保留当前路径，去除上次的路径
        path.push(item.city), // 添加当前节点
        item.children.length 
        ? treeFlat(item.children,level+1, path, res) //有子节点，继续递归
        : res.push(path.toString()) //到叶子节点，设置路径结果
    })
    return res;
}
treeFlat(data);

Answer 3

Answer 4

function list2tree(arr) {
    var ret = [];
    for (var i = 0; i < arr.length; ++i) {
        var keys = arr[i].split(","), list = ret;
        find: for (var j = 0; j < keys.length; ++j) {
            for (var k = 0; k < list.length; ++k) {
                if (keys[j] === list[k].city) {
                    list = list[k].children;
                    continue find;
                }
            }
            var obj = { city: keys[j], children: [] };
            list.push(obj);
            list = obj.children;
        }
    }
    return ret;
}
console.dir(list2tree([
    "浙江,宁波,鄞州区",
    "浙江,宁波,江北区",
    "浙江,杭州,富阳",
    "浙江,杭州,上城区",
    "上海,黄浦区"
]));

补充个反向转换且不用递归的解法：

function tree2list(arr) {
    var ret = [];
    var values = [];
    var stack = arr.slice();
    var depth = [stack.length];
    while (stack.length) {
        var top = stack.shift();
        values.push(top.city);
        if (top.children.length) {
            stack.unshift.apply(stack, top.children);
            depth.push(top.children.length);
        } else {
            ret.push(values.join());
            do {
                values.pop();
            } while (--depth[depth.length - 1] === 0 && !depth.pop());
        }
    }
    return ret;
}
console.dir(tree2list([{
    city: '浙江',
    children: [{
        city: '宁波',
        children: [{
            city: '鄞州区',
            children: []
        }, {
            city: '江北区',
            children: []
        }]
    }, {
        city: '杭州',
        children: [{
            city: '富阳',
            children: []
        }, {
            city: '上城区',
            children: []
        }]
    }]
}, {
    city: '上海',
    children: [{
        city: '黄浦区',
        children: []
    }]
}]));