二叉树的层平均值

• https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

描述

• 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值
• 与实际答案相差 $10^{-5}$ 以内的答案可以被接受

示例 1

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]

解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11
因此返回 [3, 14.5, 11]

示例 2

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

提示

• 树中节点数量在 [1, $10^4$] 范围内
• -$2^{31}$ <= Node.val <= $2^{31}$ - 1

Typescript 版算法实现

1 ) 方案1：深度优先搜索

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(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)*     }* }*/function averageOfLevels(root: TreeNode | null): number[] {function dfs(node: TreeNode | null, level: number, totals: number[], counts: number[]): void {if (!node) return;if (level < totals.length) {totals[level] += node.val;counts[level] += 1;} else {totals.push(node.val);counts.push(1);}if (node.left) dfs(node.left, level + 1, totals, counts);if (node.right) dfs(node.right, level + 1, totals, counts);}const totals: number[] = [];const counts: number[] = [];if (root) dfs(root, 0, totals, counts);return totals.map((total, index) => total / counts[index]);
}

2 ) 方案2：广度优先搜索

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(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)*     }* }*/function averageOfLevels(root: TreeNode | null): number[] {const averages: number[] = [];const queue: TreeNode[] = [root];while (queue.length > 0) {let total = 0;const size = queue.length;for (let i = 0; i < size; i++) {const node = queue.shift()!;total += node.val;if (node.left) {queue.push(node.left);}if (node.right) {queue.push(node.right);}}averages.push(total / size);}return averages;
}