LeetCode - Maximum Depth of N-ary Tree

LeetCode の Maximum Depth of N-ary Tree を解いてみます。

問題の概要

• インプット（引数）
  • N個のNodeを持つツリー
• アウトプット（引数）
  • ツリーの中の中の最大の深さ
  • 最大の深さ = root Nodeから最も遠いリーフNodeまでの最長パス上のNodeの数

ツリーの各Nodeを表現するクラスは以下のように定義されています

import java.util.List;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

答え

各リーフNode（childが存在しない）まで再帰的に探索して深さを導いて、その最大値を返します。

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int max = 0;
        for (Node child : root.children) {
            max = Math.max(max, maxDepth(child));
        }
        return 1 + max;
    }
}