199. 二叉树的右视图

题目链接

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 validate() {
    const input = [];
    const root = initTree(input);
    console.log('root', root);
    const result = rightSideView(root);
    console.log(result);
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if (!root) return [];
    let queue = [root];
    let rightSideList = [];
    while(queue.length) {
        const curLevelLen = queue.length;
        for(let i=0;i<curLevelLen; i++) {
            const curNode = queue.pop();
            if (i==curLevelLen-1) {
                // 最右侧节点
                rightSideList.push(curNode.val);
            }
            // 否则更新下一层节点
            if(curNode.left)queue.unshift(curNode.left);
            if(curNode.right)queue.unshift(curNode.right);
        }
    }
    return rightSideList;
};


validate();