字符串构建树

练习树的算法时，使用代码手动构造树比较麻烦，容易出错，用 JSON 来表示也不够方便，用直观的字符串来表示一颗树更简单 (用缩进来表示节点的父子关系)，例如:

1
    2
    3
        5
        6
    4
        7
            9
            10
        8
    11

下面就解析这个字符串生成一棵树:

/**
 * 缩进数量，每 4 个空格作为一个缩进
 *
 * @param {String} line 字符串
 * @return {Int} 返回缩进的个数
 */
function countIndent(line) {
    return (line.lastIndexOf(' ') + 1) / 4;
}

/**
 * 使用树结构的字符串构建树
 *
 * @param {String} treeContent 树结构的字符串
 * @return {JSON} 返回树的根节点
 */
function buildTree(treeContent) {
    // 1. 按行分割，每一行是一个节点信息
    // 2. 数组的第一个元素构造根节点
    // 3. 从数组的第二个元素开始
    //    3.1 构造一个节点，加入到节点的数组中
    //    3.2 在节点数组中从后往前查找最近一个比当前节点少一个缩进的节点，此节点为当前节点的父节点

    // [1] 按行分割，每一行是一个节点信息
    var lines = treeContent.split('\n').filter(line => line.length > 0);

    if (lines.length === 0) {
        return null;
    }

    // [2] 数组的第一个元素构造根节点
    var root  = { id: parseInt(lines[0]), indent: 0 };
    var nodes = [root];

    for (let i = 1; i < lines.length; i++) {
        // [3.1] 构造一个节点，加入到节点的数组中
        var indent = countIndent(lines[i]);
        var node   = { id: parseInt(lines[i]), indent: indent };
        nodes.push(node);

        // [3.2] 在节点数组中从后往前查找最近一个比当前节点少一个缩进的节点，此节点为当前节点的父节点
        for (let j = nodes.length-1; j >= 0; j--) {
            if (nodes[j].indent === indent-1) {
                nodes[j].children = nodes[j].children || [];
                nodes[j].children.push(node);
                break;
            }
        }
    }

    return root;
}

// 树结构的字符串 (缩进使用 4 个空格)
var treeContent = `
1
    2
    3
        5
        6
    4
        7
            9
            10
        8
    11
`;

var treeRoot = buildTree(treeContent);
console.log(JSON.stringify(treeRoot));