当前位置： 面试刷题>> 二叉树的层平均值(经典算法150题)
### 题目描述
给定一个二叉树，请编写一个函数来计算二叉树每一层的平均值。二叉树中节点的值可能为正整数、负整数或零。该函数将返回一个包含每一层平均值的数组，其中索引`i`处的元素表示二叉树第`i+1`层的平均值（假设根节点位于第1层）。
### 示例
给定以下二叉树：
```
3
/ \
9 20
/ \
15 7
```
返回的结果应为`[3, 14.5]`，其中`3`是根节点所在第一层的平均值（只有一个节点），`14.5`是第二层（9, 20）的平均值，第三层（15, 7）的平均值未被计算，因为它不是最外层的节点。
### PHP 代码示例
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function averageOfLevels($root) {
if ($root === null) {
return [];
}
$result = [];
$queue = new SplQueue();
$queue->enqueue($root);
while (!$queue->isEmpty()) {
$levelSize = $queue->count();
$sum = 0;
for ($i = 0; $i < $levelSize; $i++) {
$node = $queue->dequeue();
$sum += $node->val;
if ($node->left !== null) {
$queue->enqueue($node->left);
}
if ($node->right !== null) {
$queue->enqueue($node->right);
}
}
$result[] = $sum / $levelSize;
}
return $result;
}
// 示例用法
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);
$averages = averageOfLevels($root);
print_r($averages);
?>
```
### Python 代码示例
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def averageOfLevels(root):
if not root:
return []
result = []
queue = [root]
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.pop(0)
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_sum / level_size)
return result
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
averages = averageOfLevels(root)
print(averages)
```
### JavaScript 代码示例
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function averageOfLevels(root) {
if (!root) return [];
let result = [];
let queue = [root];
while (queue.length > 0) {
let levelSize = queue.length;
let levelSum = 0;
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
levelSum += node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(levelSum / levelSize);
}
return result;
}
// 示例用法
let root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
let averages = averageOfLevels(root);
console.log(averages);
```
在以上示例中，我们使用了广度优先搜索（BFS）来遍历二叉树的每一层，并使用队列来辅助实现。对于每一层，我们计算其所有节点的值之和，然后除以该层的节点数来得到平均值，并将结果存储在数组中。