输了就是输了，这说明什么呀，小朋友，还得练。

前端面试中常见的一个题目：如何将一个扁平化数组转化为树形结构？

情景一

例如，有数组arr结构如下：

const arr = [
    { id: 1, pid: 0 },
    { id: 2, pid: 1 },
    { id: 3, pid: 1 },
    { id: 4, pid: 2 },
    { id: 5, pid: 2 },
    { id: 6, pid: 3 },
];

将其转化为如下树形结构结构：

{
    "id": 0,
    "children": [
        {
            "id": 1,
            "children": [
                {
                    "id": 2,
                    "children": [
                        {
                            "id": 4
                        },{
                            "id": 5
                        }
                    ]
                },
                {
                    "id": 3,
                    "children": [
                        {
                            "id": 6
                        }
                    ]
                }
            ]
        }
    ]
}

解题思路：

1. 先将数组元素转化成对象结构（hash结构）去存储
   
2. 将hash结构数据转化为树形结构数据

解题代码：

function arr2Tree (arr) {
  // parentHash用于确定rootId,childHash用于构建树形结构
  //步骤一：转化数组数据称为hash结构数据
  const parentHash = {}, childHash = {};
  for (let item of arr) {
    const { id, pid } = item;
    parentHash[id] = pid;

    if (!childHash[pid]) {
      childHash[pid] = [];
    }
    childHash[pid].push(id);
  }

  //步骤二：确定树形结构的根节点
  let rootId = arr[0].id;
  while (parentHash[rootId] !== undefined) {
    rootId = parentHash[rootId];
  }
  console.log(rootId)

  //步骤三：将hash结构转化为树形结构
  return hash2Tree(childHash, rootId);

}

//函数作用：将hash结构转化为树形结构
function hash2Tree (childHash, rootId) {
  let res = { id: rootId };
  if (childHash[rootId] && childHash[rootId].length > 0) {
    res.children = childHash[rootId].map((cid) => hash2Tree(childHash, cid))
  }
  return res;
}

最终结果：

情景二：HTML转AST

输入:  let str ="<div><span>tests</span></div>"
输出 : {
  tag: 'div',
  children: [
    {
      tag: 'span'
    },
  ],
}

解题代码：

 // 设置每个节点标签属性
// let attrRE = /\s([^'"/\s><]+?)[\s/>]|([^\s=]+)=\s?(".*?"|'.*?')/g;
 function parseTag(tag) {
   let res = {
     type: "tag",
     name: "",
     voidElement: false,
     attrs: {},
     children: [],
   };
   let tagMatch = tag.match(/<\/?([^\s]+?)[/\s>]/);
   if (tagMatch) {
     // 标签名称为正则匹配的第2项
     res.name = tagMatch[1];
     if (tag.charAt(tag.length - 2) === "/") {
       // 判断tag字符串倒数第二项是不是 / 设置为空标签。 例子：<img/>
       res.voidElement = true;
     }
   }
   // 匹配所有的标签正则
   let classList = tag.match(/\s([^'"/\s><]+?)\s*?=\s*?(".*?"|'.*?')/g);

   if (classList && classList.length) {
     for (let i = 0; i < classList.length; i++) {
       // 去空格再以= 分隔字符串  得到['属性名称','属性值']
       let c = classList[i].replace(/\s*/g, "").split("=");
       // 循环设置属性
       if (c[1]) res.attrs[c[0]] = c[1].substring(1, c[1].length - 1);
     }
   }
   return res;
 }

 function parse(html) {
   let result = [];
   let current;
   let level = -1;
   let arr = [];
   let tagRE = /<[a-zA-Z\-\!\/](?:"[^"]*"['"]*|'[^']*'['"]*|[^'">])*>/g;

   html.replace(tagRE, function (tag, index) {
     // 判断第二个字符是不是'/'来判断是否open
     let isOpen = tag.charAt(1) !== "/";
     // 获取标签末尾的索引
     let start = index + tag.length;
     // 标签之前的文本信息
     let text = html.slice(start, html.indexOf("<", start));

     let parent;
     if (isOpen) {
       level++;
       // 设置标签属性
       current = parseTag(tag);
       // 判断是否为文本信息，是就push一个text children  不等于'  '
       if (!current.voidElement && text.trim()) {
         current.children.push({
           type: "text",
           content: text,
         });
       }
       // 如果我们是根用户，则推送新的基本节点
       if (level === 0) {
         result.push(current);
       }
       // 判断有没有上层，有就push当前标签
       parent = arr[level - 1];
       if (parent) {
         parent.children.push(current);
       }
       arr[level] = current;
     }
     // 如果不是开标签，或者是空元素：</div><img>
     if (!isOpen || current.voidElement) {
       // level--
       level--;
     }
   });
   return result;
 }
 // test str:
 let html = `
             <div class = 'divClass' style='backgroud:url(./src/asset/img.jpg)' type='c'>
               朱文本
               <span>文本1</span>  
               <p class='names'>
                 文本2
                 <div>
                   <span class="span"></span>
                 </div>
                 <img/>
               </p>
             </div>
           `;

 let ast = parse(html);
 console.log(ast);