559. N叉树的最大深度
2018-11-18 本文已影响49人
闭门造折
给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如
给定一个 3叉树 :
1
/|\
3 2 4
/ \
5 6
我们应返回其最大深度,3。
说明:
树的深度不会超过 1000。
树的节点总不会超过 5000。
思路1
使用递归,找到当前节点所有孩子节点中最深的一支,+1即为当前节点深度
性能分析
时间复杂度为O(N),空间复杂度最优为O(LogN),最差为O(N)(全部为单支)
具体代码
int max(int a, int b){ // 辅助函数,用来返回较大值
return a > b ? a : b;
}
int maxDepth(Node* root) {
if(root == NULL){ //空节点过滤
return 0;
}
int res = 0;
for(int i = 0; i < root->children.size(); i++){ // 遍历每个子节点
res = max(res, maxDepth(root->children[i])); // 选择最大子树深度
}
return 1 + res; // 最大子树深度 + 1 = 当前树深度
}
思路2
使用迭代,一层一层的遍历,每次把某一层的节点全部找出来,直到找不到下一层为止
存放的数据结构可以用队列,先进先出,后方插入前方弹出
性能分析
时间复杂度为O(N),空间复杂度为O(N)
具体代码
queue<Node*> q;
int maxDepth(Node* root) {
if(root == NULL) return 0; // 空节点筛除
int res = 0;
q.push(root);
while(q.size()){ // 当该层还有节点
for(int i = q.size(); i > 0; i--){ // 遍历该层所有节点
Node* t = q.front(); // 获得队列头元素
q.pop(); // 弹出队列头元素
// 向队列尾插入队列头元素所有子节点
for(int j = 0; j < t->children.size(); j++){
q.push(t->children[j]);
}
}
// 层数++
res++;
}
return res;
}