/**
  需要输出
    [{
        "name": "h3"
    }, {
        "name": "h2",
        "child": [{
            "name": "h3"
        }]
    }, {
        "name": "h1",
        "child": [{
            "name": "h2",
            "child": [{
                "name": "h3"
            }, {
                "name": "h3"
            }]
        }, {
            "name": "h2",
            "child": [{
                "name": "h3"
            }]
        }]
    }, {
        "name": "h1",
        "child": [{
            "name": "h2",
            "child": [{
                "name": "h4"
            }]
        }, {
            "name": "h2",
            "child": [{
                "name": "h3"
            }]
        }]
    }]
 */

let list = [
  'h3',
  'h2', 'h3',
  'h1', 'h2', 'h3', 'h3', 'h2', 'h3',
  'h1', 'h2', 'h4', 'h2', 'h3'
]

function makeTree(arr) {
  let tree = [];
  let max = Infinity
  let prev = {};

  arr.forEach((title) => {
    let level = Number(title[1]);
    if (level <= max) {
      let node = {
        name: title,
      };
      tree.push(node);
      prev.level = level;
      prev.node = node;
      max = level
    } else if (level === prev.level) {
      // 等级相同的话 上级节点的child继续增加子节点
      prev = prev.prev;
      pushNodeAndAdvanceQueue();
    } else if (level > prev.level) {
      pushNodeAndAdvanceQueue();
    } else {
      while (level <= prev.level) {
        // 向上回溯，找到平级的再上一层node
        prev = prev.prev;
      }
      pushNodeAndAdvanceQueue();
    }

    function pushNodeAndAdvanceQueue() {
        let node = {
            name: title,
        };
        if (!prev.node.child) {
            let child = [];
            prev.node.child = child;
        }
        prev.node.child.push(node);
        let next = {
          level,
          node,
          prev,
        };
        prev = next;
    }
  });

  return tree;
}

console.log(makeTree(list));

/**
 * 思路
 * 
 * 利用链表来向上回溯合适的父节点
 * 利用max变量记录当前分组的最大标题，如果比max还大，就需要新开一个分组了。
 */