← Static tasks

1522. Diameter of N-Ary Tree

leetcode medium

#array#csharp#leetcode#math#medium#recursion#sort#tree

Task

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

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

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

Пример:

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

Output: 3

Explanation: Diameter is shown in red color.

C# solution

matched/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++ solution

auto-draft, review before submit
#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 solution

matched/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 solution

matched/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 solution

matched/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 solution

matched/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
}

Explanation

Algorithm

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

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

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

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

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

😎