Leetcode 429. N-ary Tree Level Order Traversal

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Recursive

/* // Definition for a Node. class Node { public:int val = NULL;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;if(!root) {return result;}queue<Node*> level;level.push(root);levelOrderTraverse(result, level);return result;}void levelOrderTraverse(vector<vector<int>>& result, queue<Node*> level) {if(level.empty()) {return;}queue<Node*> nextLevel;vector<int> values;while(!level.empty()) {Node* current = level.front();level.pop();values.push_back(current->val);for(int i = 0; i < current->children.size(); i++) {nextLevel.push(current->children[i]);}}result.push_back(values);levelOrderTraverse(result, nextLevel);}
};

• Iterative

/* // Definition for a Node. class Node { public:int val = NULL;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;if(!root) {return result;}queue<Node*> level;level.push(root);levelOrderTraverse(result, level);return result;}void levelOrderTraverse(vector<vector<int>>& result, queue<Node*> level) {if(level.empty()) {return;}while(!level.empty()) {queue<Node*> nextLevel;vector<int> values;while(!level.empty()) {Node* current = level.front();level.pop();values.push_back(current->val);for(int i = 0; i < current->children.size(); i++) {nextLevel.push(current->children[i]);}}result.push_back(values);level = nextLevel;}}};

Reference

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