一、题目
二、思路
思路一:递归
for循环,每次判断deep与每一个子树深度的大小;注意不要用三目运算符,会进行两次重复的递归,超出时间
思路二:层次遍历
利用队列来解决,首先添加头结点,然后定义一个指针等于这个节点,添加进这个节点的子节点,删除这个头结点
三、思路一代码
/*
// 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 deep=0;
for(int i=0;i<root->children.size();++i)
{
deep=max(deep,maxDepth(root->children[i]));
}
return deep+1;
}
};
四、思路二代码
/*
// 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;
}
queue<Node*>Que;
Que.push(root);
int deep=0;
while(!Que.empty())
{
deep++;
int size=Que.size();
for(int j=0;j<size;++j)
{
Node *p=Que.front();
for(int i=0;i<p->children.size();++i)
{
Que.push(p->children[i]);
}
Que.pop();
}
}
return deep;
}
};