1522. Diameter of N-Ary Tree

LeetCode medium original: C# #array #csharp #leetcode #math #medium #recursion #sort #tree

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

LeetCode Static

given корневое Baum N-арности, нужно вычислить длину диаметра дерева.

Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.

(Eingabeная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)

Beispiel:

Input: root = [1,null,3,2,4,null,5,6]

Output: 3

Explanation: Diameter is shown in red color.

C# Lösung

zugeordnet/original

public class Solution {
    private int diameter = 0;
    private int Height(Node node) {
        if (node.children.Count == 0) return 0;
        int maxHeight1 = 0, maxHeight2 = 0;
        foreach (var child in node.children) {
            int parentHeight = Height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            int distance = maxHeight1 + maxHeight2;
            diameter = Math.Max(diameter, distance);
        }
        return maxHeight1;
    }
    public int Diameter(Node root) {
        diameter = 0;
        Height(root);
        return diameter;
    }
}

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:
    private int diameter = 0;
    private int Height(Node node) {
        if (node.children.size() == 0) return 0;
        int maxHeight1 = 0, maxHeight2 = 0;
        foreach (var child in node.children) {
            int parentHeight = Height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            int distance = maxHeight1 + maxHeight2;
            diameter = max(diameter, distance);
        }
        return maxHeight1;
    }
    public int Diameter(Node root) {
        diameter = 0;
        Height(root);
        return diameter;
    }
}

Java Lösung

zugeordnet/original

class Solution {
    protected int diameter = 0;

    protected int height(Node node) {
        if (node.children.size() == 0)
            return 0;

        int maxHeight1 = 0, maxHeight2 = 0;
        for (Node child : node.children) {
            int parentHeight = height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            int distance = maxHeight1 + maxHeight2;
            this.diameter = Math.max(this.diameter, distance);
        }

        return maxHeight1;
    }

    public int diameter(Node root) {
        this.diameter = 0;
        height(root);
        return diameter;
    }
}

JavaScript Lösung

zugeordnet/original

class Solution {
    constructor() {
        this.diameter = 0;
    }

    height(node) {
        if (node.children.length === 0) return 0;

        let maxHeight1 = 0, maxHeight2 = 0;
        for (const child of node.children) {
            const parentHeight = this.height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            const distance = maxHeight1 + maxHeight2;
            this.diameter = Math.max(this.diameter, distance);
        }

        return maxHeight1;
    }

    diameter(root) {
        this.diameter = 0;
        this.height(root);
        return this.diameter;
    }}

Python Lösung

zugeordnet/original

class Solution:
    def __init__(self):
        self.diameter = 0

    def height(self, node):
        if not node.children:
            return 0

        maxHeight1, maxHeight2 = 0, 0
        for child in node.children:
            parentHeight = self.height(child) + 1
            if parentHeight > maxHeight1:
                maxHeight2 = maxHeight1
                maxHeight1 = parentHeight
            elif parentHeight > maxHeight2:
                maxHeight2 = parentHeight
            distance = maxHeight1 + maxHeight2
            self.diameter = max(self.diameter, distance)
        return maxHeight1

    def diameter(self, root):
        self.diameter = 0
        self.height(root)
        return self.diameter

Go Lösung

zugeordnet/original

type Node struct {
    Val      int
    Children []*Node
}

type Solution struct {
    diameter int
}

func (s *Solution) height(node *Node) int {
    if len(node.Children) == 0 {
        return 0
    }

    maxHeight1, maxHeight2 := 0, 0
    for _, child := range node.Children {
        parentHeight := s.height(child) + 1
        if parentHeight > maxHeight1 {
            maxHeight2 = maxHeight1
            maxHeight1 = parentHeight
        } else if parentHeight > maxHeight2 {
            maxHeight2 = parentHeight
        }
        distance := maxHeight1 + maxHeight2
        if distance > s.diameter {
            s.diameter = distance
        }
    }

    return maxHeight1
}

func (s *Solution) Diameter(root *Node) int {
    s.diameter = 0
    s.height(root)
    return s.diameter
}

Algorithm

Определите функцию height(node), которая returns высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.

Существует два подхода для выбора двух наибольших высот:

— Первый способ заключается в хранении высот всех дочерних узлов в Arrayе, последующей сортировке Arrayа и выборе двух наибольших elementов.

— Второй способ использует две переменные, которые отслеживают текущие два наибольших значения. Во время итерации по всем высотам эти переменные обновляются соответствующим образом.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.