原文链接 [每日 LeetCode] 559. Maximum Depth of N-ary Tree
Description:
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.
本题要求 N 叉树的最大深度,可参考[每日 LeetCode] 104. Maximum Depth of Binary Tree 的思想,使用递归和非递归方法。
-
递归方法。主函数中使用递归,首先判空,否则就是遍历子结点数组,然后对每个子结点调用递归函数的返回值加 1 后跟 res 相比,取较大值更新结果 res 即可。
-
非递归方法。借助队列 queue,BFS 的经典,对 N 叉树进行遍历,并及时更新最大深度。
C++ 代码(递归)
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int maxDepth(Node* root) {
if (!root) return 0;
int res = 1;
for (auto child : root->children) {
res = max(res, maxDepth(child) + 1);
}
return res;
}
};
运行时间:148ms
运行内存:32.1M
C++ 代码(非递归)
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int maxDepth(Node* root) {
if (!root) return 0;
int res = 0;
queue<Node*> q{{root}};
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
auto t = q.front();
q.pop();
for (auto child : t->children) {
if (child)
q.push(child);
}
}
++res;
}
return res;
}
};
运行时间:140ms
运行内存:32.8M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于