练习题2-树形相关

[coolpail]

题目

//输入以下有序的list数组
var list = [
    'h3',
    'h2', 'h3',
    'h1', 'h2', 'h3', 'h3', 'h2', 'h3',
    'h1', 'h2', 'h4', 'h2', 'h3',s
]
//输出以下树形数组结构
[
    {
        name: 'h3',
        child: []
    },
    {
        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'}]
            }
        ]
    }
]

思路

1. 独立维护一份数组list
2. 每次push时，先判断list的最后一个元素，是否比当前要push的元素大，则list元素pop出最后一个，在比较；小则当前最后一个元素的child中添加进该元素，并且list数组push进该元素

let stacks = [];

function createNode(key) {
    return {
        name: key,
        child: []
    }
}

function task(node, key) {
    stacks.push({
        name: key,
        node: node
    })
}

function Compare(k1, k2) {
    return Number(k1.slice(1)) <= Number(k2.slice(1))
}

function insert(el) {
    let _t = stacks[stacks.length - 1];
    if (!stacks.length) {
        let newnode = createNode(el);
        result.push(newnode);
        task(newnode, el);
    } else {
        if (Compare(el, _t.name)) {
            stacks.pop();
            insert(el)
        } else {
            let newnode = createNode(el);
            _t.node.child.push(newnode);
            task(newnode, el);
        }
    }
}

let list = []
let total = 1000000
for(let i = 0; i < total; i++) {
    list.push('h' + Math.floor(Math.random() * 10 + 1))
}

let result = []
list.forEach(insert);

[coolpail]

stacks的作用是：

1. 每次存入最后处理完的值（也就是确定了这个值的位置）
   2.每次新加入的值要与最后一个值比较
   2.1.比较结果第一种可作为最后一个值的child，就push进去，并且在stacks中push进这个值
   2.2比较结果第二种不可作为最后一值的child，则pop出最后一个值，再与最后一个值比较，重复上述，最后确定位置

这边有用到引用数据的，push进去地址不变，值的内容发生变化