当前位置: 面试刷题>> 二叉树的层平均值(经典算法150题)


题目描述

给定一个二叉树,请编写一个函数来计算二叉树每一层的平均值。二叉树中节点的值可能为正整数、负整数或零。该函数将返回一个包含每一层平均值的数组,其中索引i处的元素表示二叉树第i+1层的平均值(假设根节点位于第1层)。

示例

给定以下二叉树:

    3
   / \
  9  20
    /  \
   15   7

返回的结果应为[3, 14.5],其中3是根节点所在第一层的平均值(只有一个节点),14.5是第二层(9, 20)的平均值,第三层(15, 7)的平均值未被计算,因为它不是最外层的节点。

PHP 代码示例

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->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 代码示例

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 代码示例

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)来遍历二叉树的每一层,并使用队列来辅助实现。对于每一层,我们计算其所有节点的值之和,然后除以该层的节点数来得到平均值,并将结果存储在数组中。

推荐面试题