# LeetCode Medium 429. N-ary Tree Level Order Traversal

tags: leetcode

Classicalの意味を一回辞書で調べてほしいと思う日々．

問題

• Explore
• Problems

アイデア

深さごとにノードの値をまとめて配列に入れ，それらの配列を1つの配列に格納します．

単にBFSをするという問題ですね．それにはQueueを使うのが便利です．

解法

• キューに現在の根を入れます
• そして，キューが空になるまで以下の処理を続けます
  • 現在キューに入っているノードの値を入れる配列を作ります
  • 現在のキューに入っているノードの値を全てその配列に入れます
  • その際にそのノードの子を全てキューに入れます
  • これが終わったらその配列を答えの配列に格納します

計算量

ノードが$N$だとする

• 時間計算量
  • $O(N)$
• 空間計算量
  • 毎回必要に成る配列は最悪$O(N)$
  • 答えに必要なものも同様に$O(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:
  vector<vector<int>> levelOrder(Node* root) {
    if (!root)
      return vector<vector<int>>();
    
    vector<vector<int>> res;
    queue<Node*> nodeQue;
    nodeQue.push(root);
    
    while (!nodeQue.empty()) {
      vector<int> curVals;
      int size = nodeQue.size();
      for (int i = 0; i < size; i++) {
        auto curNode = nodeQue.front();
        nodeQue.pop();
        curVals.push_back(curNode->val);
        for (auto& child : curNode->children)
          nodeQue.push(child);
      }
      res.push_back(curVals);
    }
    return res;
  }
};