经典150题 - 二叉树层序遍历

199. 二叉树的右视图

var rightSideView = function(root) {
    if(!root) return []
    const res = [root.val]
    const queue = [root]
 
    while(queue.length) {
        let len = queue.length
        for(let i=0; i<len; i++) {
            const node = queue.shift()
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
            if(i===len-1 && queue.length) {
                res.push(queue[queue.length-1].val)
            }
        }
    }
    return res
};

637. 二叉树的层平均值

var averageOfLevels = function(root) {
    const res = []
    const queue = [root]
    while(queue.length) {
        const len = queue.length
        let sum = 0
        for(let i = 0; i<len;i++) {
            const node = queue.shift()
            sum+=node.val
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(sum/len)
    }
    return res
};

102. 二叉树的层序遍历

var levelOrder = function(root) {
    if(!root) return []
    const res = []
    const queue = [root]
    while(queue.length) {
        let len = queue.length
        const curr = []
        while(len--) {
            const node = queue.shift()
            curr.push(node.val)
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(curr)
    }
    return res
};

103. 二叉树的锯齿形层序遍历

var zigzagLevelOrder = function(root) {
    if(!root) return []
    const res = []
    const queue = [root]
 
    while(queue.length) {
        let len = queue.length
        const isPush = res.length % 2 === 0
        const curr = []
        while(len--) {
            const node = queue.shift()
            isPush ? curr.push(node.val) : curr.unshift(node.val)
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        res.push(curr)
    }
 
    return res
};

相关笔记

• 树与二叉树基础
• 二叉树专题
• 二叉树其他题目
• GRD 二叉树刷题