1522. Diameter of N-Ary Tree

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium #recursion #sort #tree

LeetCode Static

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

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

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

Пример:

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

Output: 3

Explanation: Diameter is shown in red color.

C# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.