# LeetCode Easy 559. Maximum Depth of N-ary Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

N-ary木の深さを測る問題です．

基本的に二分木と同じように解けます．(繰り返し文を使う必要があるかどうかくらいです)

解法1(recursive)

再帰関数を使ってDFSをして，深さを求めます．

• 根がないなら$0$
• そうでないなら深さを$0$で初期化します
• 深さを再帰的にmaxDepthを実行した値で更新します．
• 関数を実行するごとに深さが+1されるようにします(だから深さを$0$で初期化するのです)

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 木の深さに応じて平均で$O(\log N)$，最悪$O(N)$です

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
  int maxDepth(Node* root) {
    if (!root)
      return 0;
    int depth(0);
    for (auto& child : root->children)
      depth = max(depth, maxDepth(child));
    return depth + 1;
  }
};

解法2(iterative)

Queueを使ってBFSをしてもStackを使ってDFSをしても解けます

ただ，書くのが面倒なので暇な時に...