637. Average of Levels in Binary Tree

LeetCode easy original: C# #array #csharp #easy #graph #leetcode #queue #tree #two-pointers

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

given корень бинарного дерева, return среднее значение узлов на каждом уровне в виде Arrayа. Принимаются ответы в пределах 10-5 от фактического ответа.

Beispiel:

Input: root = [3,9,20,null,null,15,7]

Output: [3.00000,14.50000,11.00000]

C# Lösung

zugeordnet/original

using System;
using System.Collections.Generic;
public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        var result = new List<double>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            long sum = 0;
            int count = queue.Count;
            for (int i = 0; i < count; i++) {
                var node = queue.Dequeue();
                sum += node.val;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.Add((double)sum / count);
        }
        return result;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<double> AverageOfLevels(TreeNode root) {
        var result = new List<double>();
        var queue = new queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.size() > 0) {
            long sum = 0;
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                var node = queue.Dequeue();
                sum += node.val;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.push_back((double)sum / count);
        }
        return result;
    }
}

Java Lösung

zugeordnet/original

import java.util.*;

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            long sum = 0;
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add((double) sum / count);
        }
        
        return result;
    }
}

JavaScript Lösung

zugeordnet/original

var averageOfLevels = function(root) {
    let result = [];
    let queue = [root];
    
    while (queue.length > 0) {
        let levelSum = 0;
        let levelCount = queue.length;
        for (let i = 0; i < levelCount; 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 / levelCount);
    }
    
    return result;
};

Python Lösung

zugeordnet/original

from collections import deque

def averageOfLevels(root):
    result = []
    queue = deque([root])
    
    while queue:
        level_sum, level_count = 0, len(queue)
        for _ in range(level_count):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_sum / level_count)
    
    return result

Go Lösung

zugeordnet/original

package main

import (
  "container/list"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func averageOfLevels(root *TreeNode) []float64 {
  var result []float64
  queue := list.New()
  queue.PushBack(root)

  for queue.Len() > 0 {
    levelSum := 0
    levelCount := queue.Len()
    for i := 0; i < levelCount; i++ {
      node := queue.Remove(queue.Front()).(*TreeNode)
      levelSum += node.Val
      if node.Left != nil {
        queue.PushBack(node.Left)
      }
      if node.Right != nil {
        queue.PushBack(node.Right)
      }
    }
    result = append(result, float64(levelSum)/float64(levelCount))
  }

  return result
}

Algorithm

Обход дерева

Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

Подсчет среднего значения

Для каждого уровня дерева подсчитайте сумму значений узлов и количество узлов, чтобы вычислить среднее значение.

Сохранение результата

Сохраните среднее значение каждого уровня в Array и return его.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.