429. N 叉树的层序遍历

题目链接

// Definition for a Node.
function Node(val,children) {
    this.val = val;
    this.children = children;
};

// 还原一棵n叉树
function initTree(dataList) {
    let curFather = -1; // father跟随datalist， 副
    let curChildren = []; // 解析当前的孩子节点, 主
    let allNodeList = [];
    dataList.forEach(el => {
        if (!el) {
            if (curFather !== -1) {
                allNodeList[curFather].children = [...curChildren];
            }
            curFather += 1;
            curChildren = [];
        } else {
            const curNode = new Node(el, []);
            allNodeList.push(curNode);
            curChildren.push(curNode);
        }
    });
    // 最后一个节点之后没有null, 因此需要对最后的节点做处理
    if (curFather !== -1) {
        allNodeList[curFather].children = [...curChildren];
    }
    return allNodeList[0];
}

function validate() {
    const input = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14];
    const tree = initTree(input);
    console.log('tree', tree);
    const res = levelOrder(tree);
    console.log('res', res);
};

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root)return [];
    const queue = [root];
    let res = [];
    while (queue.length) {
        let curLevel = [];
        const levelLen = queue.length;
        for(let i=0;i<levelLen;i++) {
            curNode = queue.pop();
            curLevel.push(curNode.val);
            if (curNode.children) {
                curNode.children.forEach(child=>{
                    queue.unshift(child);
                });
            }
        }
        res.push(curLevel);
    }
    return res;
};

validate();