102. 二叉树的层序遍历【中等题】

题目链接

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * 还原一棵满二叉树(似乎和题目用例不太一样？)
 * @param {number[]} valList 
 * @returns {TreeNode root}
 */
function initTree(valList) {
    const treeNodeList = [];
    const sum = valList.length;
    // 记住节点索引
    valList.forEach((el, index) => {
        if (!el) {
            treeNodeList.push(null);
            return;
        }
        const leftIndex = index*2+1 < sum ? index*2+1: null;
        const rightIndex = index*2+2 < sum ? index*2+2 :null;
        const newNode = new TreeNode(el, leftIndex, rightIndex);
        treeNodeList.push(newNode);
    });
    // 将节点索引替换为节点
    treeNodeList.forEach(node=>{
        if(node && node.left) {
            node.left = treeNodeList[node.left];
        }
        if(node && node.right){
            node.right = treeNodeList[node.right];
        }
    });
    return treeNodeList[0];
}

function obj2array(obj) {
    const res = [];
    Object.keys(obj).forEach(key=>{
        res.push(obj[key]);
    });
    return res;
}
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    let queue = [root];
    let resObj = {};
    root.level = 0;
    while(queue.length) {
        const curNode = queue.pop();
        const nextLevel = curNode.level + 1;
        if (!resObj[curNode.level]) {
            resObj[curNode.level] = [];
        }
        resObj[curNode.level].push(curNode.val);
        if(curNode.left) {
            curNode.left.level = nextLevel;
            queue.unshift(curNode.left);
        }
        if(curNode.right) {
            curNode.right.level = nextLevel;
            queue.unshift(curNode.right);
        }
    }
    const res = obj2array(resObj);
    return res;
};

function validate() {
    const input = [2];
    // const input = [3,9,20,null,null,15,7];
    const root = initTree(input);
    console.log('root', root);
    const result = levelOrder(root);
    console.log('result', result);
}

validate();