559. Maximum Depth of N-ary Tree

leetcode easy

#csharp#easy#graph#leetcode#recursion#search#tree

Task

Дано n-арное дерево, найдите его максимальную глубину.

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

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

Пример:

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

Output: 3

C# solution

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

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 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

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

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

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

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

Explanation

Algorithm

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

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

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

😎