559. Maximum Depth of N-ary Tree

LeetCode easy original: C# #csharp #easy #graph #leetcode #recursion #search #tree

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

given n-арное arbre, find его максимальную глубину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. Exempleы).

Exemple:

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

Output: 3

C# solution

correspondant/original

class Solution {
    public int MaxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.Count == 0) {
            return 1;
        } else {
            List<int> heights = new List<int>();
            foreach (var child in root.children) {
                heights.Add(MaxDepth(child));
            }
            return heights.Max() + 1;
        }
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#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 int MaxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.size() == 0) {
            return 1;
        } else {
            List<int> heights = new List<int>();
            foreach (var child in root.children) {
                heights.push_back(MaxDepth(child));
            }
            return heights.Max() + 1;
        }
    }
}

Java solution

correspondant/original

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;  
        } else {
            List<Integer> heights = new LinkedList<>();
            for (Node item : root.children) {
                heights.add(maxDepth(item)); 
            }
            return Collections.max(heights) + 1;
        }
    }
}

JavaScript solution

correspondant/original

class Solution {
    maxDepth(root) {
        if (root === null) {
            return 0;
        } else if (root.children.length === 0) {
            return 1;
        } else {
            let heights = root.children.map(child => this.maxDepth(child));
            return Math.max(...heights) + 1;
        }
    }
}

Python solution

correspondant/original

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0
        elif not root.children:
            return 1
        else:
            heights = [self.maxDepth(child) for child in root.children]
            return max(heights) + 1

Go solution

correspondant/original

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

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    } else if len(root.Children) == 0 {
        return 1
    } else {
        heights := []int{}
        for _, child := range root.Children {
            heights = append(heights, maxDepth(child))
        }
        max := 0
        for _, h := range heights {
            if h > max {
                max = h
            }
        }
        return max + 1
    }
}

Algorithm

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

Здесь мы демонстрируем Exemple с использованием стратегии поиска в глубину (DFS - Depth First Search).

Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.