# LeetCode 559 N叉树的最大深度[dfs bfs] HERODING的LeetCode之路

``````/*
// 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:
int depth = 0;
int maxDepth(Node* root) {
if(root == nullptr) {
return 0;
}
dfs(root, 1);
return depth;
}

void dfs(Node* root, int count) {
if(root->children.size() == 0) {
depth = max(depth, count);
return;
}
for(auto child : root->children) {
dfs(child, count + 1);
}
}
};
``````

bfs的方法也是很简单，就是逐层遍历呗，不断放入队列中，直到队列中没有节点了，返回最大深度，代码如下：

``````/*
// 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:
int maxDepth(Node* root) {
if(root == nullptr) {
return 0;
}
int depth = 0;
queue<Node*> q;
q.push(root);
while(!q.empty()) {
int len = q.size();
for(int i = 0; i < len; i ++) {
Node* node = q.front();
q.pop();
for(auto& child : node->children) {
q.push(child);
}
}
depth ++;
}
return depth;
}
};

``````

THE END