第347题(2020-11-25)：算法：js实现将一个二维数组转换成树结构（京东）

[qappleh]

例如：将下面的二维数组：

var arr = [
    ["a", "aa", "aaa", "aaaa"],
    ["b", "bb", "bbb"],
    ["a", "ab", "aba"],
    ["a", "aa", "aab"]
]

转成下面树结构的对象数组：

[{
    "name" : "a",
    "child" : [
        {
            "name" : "aa",
            "child" : [
                {
                    "name" : "aaa",
                    "child" : [
                        {
                            "name" : "aaaa",
                            "child" : []
                        }
                    ]
                },
                {
                    "name" : "aab",
                    "child" : []
                }
            ]
        },
        {
            "name" : "ab",
            "child" : [
                {
                    "name": "aba",
                    "child" : []
                }
            ]
        }
    ]
},
{
    "name": "b",
    "child" : [
        {
            "name" : "bb",
            "child" : [
                {
                    "name" : "bbb",
                    "child" : []
                }
            ]
        }
    ]
}]

[Wfield]

function ArrayStack(arr) {
    this.stack = arr.sort((a, b) => a.length - b.length);
}

ArrayStack.prototype.pop = function () {
    const currentLastArr = this.stack[this.stack.length - 1];
    const node = currentLastArr.pop();
    this.stack = this.stack.sort((a, b) => a.length - b.length)
    return node;
}

ArrayStack.prototype.getLevel = function () {
    return this.stack[this.stack.length - 1].length;
}

function arr2tree() {
    let nodeList = [];
    let levelNodes = [];
    let currLevel;

    function checkLevel(leafNode, level) {
        if (currLevel === level) {
            if (levelNodes.includes(leafNode)) {
                return true;
            }
            levelNodes.push(leafNode);
        } else {
            currLevel = level;
            levelNodes = [leafNode];
        }
    }

    function makeTree(leafNode, level) {
        if (checkLevel(leafNode, level)) return nodeList;
        const parentNode = { name: leafNode, child: [] };
        nodeList = nodeList.filter((item) => {
            const isChild = item.name.startsWith(leafNode);
            if (isChild) {
                parentNode.child.push(item);
            }
            return !isChild;
        });
        nodeList.push(parentNode);
        return nodeList;
    }
    return makeTree;
}

const travel = (arr = []) => {
    let res = [];
    let stack = new ArrayStack(arr);
    let level = stack.getLevel();
    let leafNode = stack.pop();
    const makeTree = arr2tree();
    while (level) {
        res = makeTree(leafNode, level);
        level = stack.getLevel();
        leafNode = stack.pop();
    }
    return res;
}

[AimWhy]

面试题 应该尽量简单吧

var arr = [
    ["a", "aa", "aaa", "aaaa"],
    ["b", "bb", "bbb"],
    ["a", "ab", "aba"],
    ["a", "aa", "aab"]
]

function arrToTreeArr(arr = []) {
    let map = new Map();
    for(let i = 0; i < arr.length; i++) {
        for(let j = 0; j < arr[i].length; j++) {
            let name = arr[i][j];
            let isRoot = j == 0;
            let hasItem = map.has(name);

            if (!hasItem){
                map.set(name, { name, child: [], isRoot })
            }
            
            if (!isRoot && !hasItem) {
                let item = map.get(name)
                let pName = arr[i][j-1];
                map.get(pName).child.push(item)
            }
        }
    }
    return [...map.values()].filter(item => item.isRoot)
}

arrToTreeArr(arr)

[terryvince]

递归实现：

function convertTree(arr) {
  let newArr = [];

  const convertItem = (childs, items) => { // 转换每一行数据
    if (items.length == 0) return childs;
    let name = items.shift();
    let findItem = childs.find((t) => t.name == name);
    if (!findItem) { // 没有相同的节点，就造一个
      let item = { name, childs: [] };
      childs.push(item);
      return convertItem(item.childs, items);
    }
    return convertItem(findItem.childs, items); // 有相同的节点就进入下一层级
  };

  arr.map(items => convertItem(newArr, items));
  return newArr;
}

[JoeWrights]

const arr2arrTree = (list) => {
  const initTree = () => {
    const map = {}
    list.forEach(item => {
      item.forEach((item2, i) => {
        map[item2] = {}
        if (i < item.length - 1) {
          map[item2].child = {
            name: item[i + 1],
            child: null,
            rootName: item[0]
          }
        }
      })
    })
    return map
  }

  const tree = initTree()

  Object.keys(tree).forEach(key => {
    tree[key].name = key
    tree[key].child && (tree[key].child.child = tree[tree[key].child.name])
    if (!tree[key].child || (tree[key].child || {}).rootName !== key) delete tree[key]
  })

  const deleteKey = (t) => {
    if (!t) return
    Object.keys(t).forEach(key => {
      while (t[key].child && t[key].child.rootName) {
        delete t[key].child.rootName
      }
      deleteKey(t[key].child)
    })
  }

  deleteKey(tree)

  return [].concat(tree)
}