面试题：写一个算法实现字符串数组按照一定格式转为树形结构

Question

const arr = [
  'root/lufei.jpg',
  'root/font/VarelaRound.ttf',
  'root/font/SourceSansPro.ttf',
  'root/img/avator.jpg',
  'root/img/favicon.jpg',
  'root/img/bg5.jpg',
  'root/img/bg4.jpg',
  'root/img/upload/a.png',
  'root/img/nt/mvvm.png',
  'root/img/nt/android.png',
  'root/img/nt/upload.png',
  'root/img/nt/js.png',
  'root/img/mvvm/a.png',
];

写一个算法把上面的数组改成下面的树形结构

{
    name:'root',
    children:[
        {
            name:'lufei.jpg'
        },
        {
            name:'root',
            children:[
                {
                    name:'font',
                    children:[
                        {
                            name:'VarelaRound.ttf'
                        },
                        {
                            name:'SourceSansPro.ttf'
                        }
                    ]
                },
                {
                    name:'img',
                    children:[
                        // 其他...
                    ]
                }
            ]
        }
    ]
}

Answer 1

解法1

用结构体可以更清晰表示节点结构关系

struct node {
  name string
  children []*node
}

可以用trie树，以/切割定义节点深度，插入时递归

// js节点数据结构
function O() {
  this.name = 'Trie'
  this.children = []
}

// 第一个匹配成功节点，用于重续前缘，插入后继节点
O.prototype.matchChild = function (part) {
  for (let i = 0; i < this.children.length; i++) {
    if (this.children[i].name == part) {
      return this.children[i]
    }
  }
  return null
}

/**
 * 
 * @param {[]string} parts 
 * @param {Number} height 
 */
O.prototype.insert = function (parts, height) {
  if (parts.length == height) {
    // 叶子节点清除当前节点的子节点
    delete this.children
    // 必须有退出机制
    return
  }

  part = parts[height]
  // 查找第一个相同的子节点
  child = this.matchChild(part)
  if (child == null) {
    // 新建子节点
    child = new O()
    child.name = part
    this.children.push(child)
  }
  // 继续搜索插入
  child.insert(parts, height + 1)
}

用题主给的数据测试代码

o = new O()

arr.map(v => {
  o.insert(v.split('/'), 0)
})
console.log(JSON.stringify(o))

效果

{
  "name": "Trie",
  "children": [
    {
      "name": "root",
      "children": [
        {
          "name": "lufei.jpg"
        },
        {
          "name": "font",
          "children": [
            {
              "name": "VarelaRound.ttf"
            },
            {
              "name": "SourceSansPro.ttf"
            }
          ]
        },
        {
          "name": "img",
          "children": [
            {
              "name": "avator.jpg"
            },
            {
              "name": "favicon.jpg"
            },
            {
              "name": "bg5.jpg"
            },
            {
              "name": "bg4.jpg"
            },
            {
              "name": "upload",
              "children": [
                {
                  "name": "a.png"
                }
              ]
            },
            {
              "name": "nt",
              "children": [
                {
                  "name": "mvvm.png"
                },
                {
                  "name": "android.png"
                },
                {
                  "name": "upload.png"
                },
                {
                  "name": "js.png"
                }
              ]
            }
          ]
        }
      ]
    },
    {
      "name": "abc",
      "children": [
        {
          "name": "img",
          "children": [
            {
              "name": "mvvm",
              "children": [
                {
                  "name": "a.png"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

解法2

也可有第二种解法使用函数,只不过看起来不那么好理解如下

function listToTree(srcList) {
  // 1.记录根位置
  let destList = []
  srcList.forEach(path => {
    // 2.待匹配项
    let pathList = path.split('/')
    // 3.将移动指针重置顶层，确保每次从根检索匹配（必须！！！）
    let levelList = destList
    // 4.遍历待询节点
    for (let name of pathList) {
      // 5.同层同名节点查找匹配
      let obj = levelList.find(item => item.name == name)
      // 6.若不存在则建立该节点
      if (!obj) {
        obj = { name, children: [] }
        levelList.push(obj)

        // 7.若当前被增节点是叶子节点，则裁剪该节点子节点属性
        if (name == pathList[pathList.length - 1]) {
          delete obj.children
        }
      }
      // 8.已有则进入下一层，继续寻找
      levelList = obj.children
    }
  })
  return destList
}


let result = listToTree(arr)
console.log(JSON.stringify(result, null, 2))