はじめに

N-aryが入力され，それを階層ごとに分け，出力する問題．

コード全文

class Solution {
public:
  vector<vector<int>> levelOrder(Node* root) {
    if (!root) return vector<vector<int>>();
    vector<vector<int>> levels;
    queue<Node*> q;
    q.push(root);
    while(!q.empty()) {
      vector<int> level;
      int n = q.size();
      while (n) {
        level.push_back(q.front()->val);
        for (const auto& child: q.front()->children) {
          q.push(child);
        }
        q.pop();
        n--;
      }
      levels.push_back(move(level));
    }
    return levels;
  }
};

解説

関数

class Solution {
public:
  vector<vector<int>> levelOrder(Node* root) {

空の木に対する処理

    if (!root) return vector<vector<int>>();

前準備

levelsには階層毎にわけたノードの集合体を格納する．

qは，BFSに用いる．

    vector<vector<int>> levels;
    queue<Node*> q;

BFS

qに初期値となるrootを代入．

    q.push(root);
    while(!q.empty()) {

同階層のノードを集める

vector<int> levelには，同一階層のノードの値が格納される．

各階層ごとにqにノードが入っているので，すべてlevelにpush_back()していく．

      vector<int> level;
      int n = q.size();
      while (n) {
        level.push_back(q.front()->val);
        for (const auto& child: q.front()->children) {
          q.push(child);
        }
        q.pop();
        n--;
      }
      levels.push_back(move(level));

終了

    }
    return levels;
  }
};

おわりに

参考

• https://leetcode.com/problems/n-ary-tree-level-order-traversal/