LeetCode：102.二叉树的层序遍历

LeetCode：102.二叉树的层序遍历

解题思路层序遍历顺序就是广度优先遍历。不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

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

function buildTree(preorder) {
    if (preorder.length === 0) return null;
    
    let root = new TreeNode(preorder[0]);
    let queue = [root];
    let i = 1;
    
    while (i < preorder.length) {
        let currentNode = queue.shift();
        
        if (preorder[i] !== null) {
            currentNode.left = new TreeNode(preorder[i]);
            queue.push(currentNode.left);
        }
        i++;
        
        if (i < preorder.length && preorder[i] !== null) {
            currentNode.right = new TreeNode(preorder[i]);
            queue.push(currentNode.right);
        }
        i++;
    }
    
    return root;
}

var levelOrder = function(root) {
    if(!root) return []
    let queue = [root];
    let len,n
    let result=[]
    while(queue.length) {
       len=queue.length
       result.push([])
        while(len--){
            n=queue.shift()
            result[result.length-1].push(n.val)
            if(n.left)queue.push(n.left)
            if(n.right)queue.push(n.right)
        }
    }
    return result
};

// 构建二叉树
let preorder = [3,9,20,null,null,15,7];
let root = buildTree(preorder);

console.log(levelOrder(root));