花花酱 LeetCode 429. N-ary Tree Level Order Traversal

By zxi on July 14, 2018

Problem

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

[
     [1],
     [3,2,4],
     [5,6]
]

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution1: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

vector<vector<int>> ans;

preorder(root, 0, ans);

return ans;

}

private:

void preorder(Node* root, int d, vector<vector<int>>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(root->val);

for (auto child : root->children)

preorder(child, d + 1, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

if (!root) return {};

vector<vector<int>> ans;

queue<Node*> q;

q.push(root);

int depth = 0;

while (!q.empty()) {

int size = q.size();

ans.push_back({});

while (size--) {

Node* n = q.front(); q.pop();

ans[depth].push_back(n->val);

for (auto child : n->children)

q.push(child);

}

++depth;

}

return ans;

}

};

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

By zxi on July 14, 2018

Problem

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maxDepth(Node* root) {

if (root == nullptr) return 0;

int depth = 0;

for (auto child : root->children)

depth = max(depth, maxDepth(child));

return depth + 1;

}

};

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

vector<int> ans;

postorder(root, ans);

return ans;

}

private:

void postorder(Node* root, vector<int>& ans) {

if (!root) return;

for (auto child : root->children)

postorder(child, ans);

ans.push_back(root->val);

}

};

Solution 2: Iterative

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto child : node->children)

s.push(child);

}

reverse(begin(ans), end(ans));

return ans;

}

};

Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

Solution1: Recursive

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

vector<int> preorder(Node* root) {

vector<int> ans;

preorder(root, ans);

return ans;

}

private:

void preorder(Node* root, vector<int>& ans) {

if (!root) return;

ans.push_back(root->val);

for (const auto& child : root->children)

preorder(child, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<int> preorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)

s.push(*it);

}

return ans;

}

};

Posts tagged as “n-ary”

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

Problem

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 589. N-ary Tree Preorder Traversal

Problem

Solution1: Recursive

Solution2: Iterative

Related Problems