116. 填充每个节点的下一个右侧节点指针

题目链接

// https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

/**
 * 还原一棵满二叉树(似乎和题目用例不太一样？)
 * @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 Node(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 =  [1,2,3,4,5,null,7];
    const root = initTree(input);
    console.log('root', root);
    const result = connect(root);
    console.log('result', result);
}

// Definition for a Node.
function Node(val, left, right, next) {
    this.val = val === undefined ? null : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
    this.next = next === undefined ? null : next;
};

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if(!root)return root;
    const queue = [root];
    while(queue.length) {
        let curLevel = [];
        const levelLen = queue.length;
        for(let i=0;i<levelLen;i++) {
            const curNode = queue.pop();
            curLevel.push(curNode);
            if(curNode.left)queue.unshift(curNode.left);
            if(curNode.right)queue.unshift(curNode.right);
        }
        curLevel.forEach((node,index)=>{
            if (index === levelLen-1) {
                node.next = null;
            } else {
                node.next = curLevel[index+1];
            }
        })
    }
    return root;
};

validate();