639. 解码方法II

• 题号：639
• 来源：LeetCode
• 难度：简单
• 标签：BFS 树 队列
• 语言：TypeScript
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-27

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

层序遍历求每层均值，与文件名不符

/**
 * @difficulty easy
 * @tags BFS,树,队列
 * @time O(n)
 * @space O(n)
 * @note 层序遍历求每层均值，与文件名不符
 * @639. 解码方法II
 */
function TreeNode(val: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

let root = new TreeNode(3, new TreeNode(9, new TreeNode(1)), new TreeNode(20, new TreeNode(15), new TreeNode(7)))

let res: number[] = []
const bfs = (root: TreeNode) => {
    let quene: TreeNode[] = [root]
    while (quene.length) {

        let sum = 0
        for (let i = 0; i < quene.length; i++) {
            sum += quene[i].val
        }
        res.push(sum / quene.length)
        // 每一轮遍历时，将队列中的节点全部取出，
        // 计算这些节点的数量以及它们的节点值之和，并计算这些节点的平均值，
        // 然后将这些节点的全部非空子节点加入队列，重复上述操作直到队列为空，遍历结束。
        let queneLength = quene.length

        for (let i = 0; i < queneLength; i++) {
            let node = quene.shift()!
            if (node.left) {
                quene.push(node.left)
            }
            if (node.right) {
                quene.push(node.right)
            }
        }

    }

}

bfs(root)
console.log(res)

源码：ts/leetcode/639. 解码方法II.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm