牛客 BM28. 二叉树的最大深度
原题链接
简单
作者:
Mr-Black
,
2023-07-16 10:10:43
,
所有人可见
,
阅读 82
题目描述
二叉树的最大深度
算法1
(递归) $O(n)$
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
void traverse(TreeNode* root, int &maxlength, int depth){
if (root == NULL){ // 如果此时还有节点,则递归为其层次遍历
return;
}
maxlength = max(depth,maxlength);
// 递归进入下一层
traverse(root->left, maxlength, depth + 1);
traverse(root -> right, maxlength, depth + 1);
}
int maxDepth(TreeNode* root) {
// write code here
int maxlength = 0;
traverse(root,maxlength,1);
return maxlength;
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
//空节点没有深度
if(root == NULL)
return 0;
//返回子树深度+1
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
算法2
层次遍历 $O(n)$
C++ 代码
class Solution {
public:
int maxDepth(TreeNode* root) {
//空节点没有深度
if(root == NULL)
return 0;
//队列维护层次后续节点
queue<TreeNode*> q;
//根入队
q.push(root);
//记录深度
int res = 0;
//层次遍历
while(!q.empty()){
//记录当前层有多少节点
int n = q.size();
//遍历完这一层,再进入下一层
for(int i = 0; i < n; i++){
TreeNode* node = q.front();
q.pop();
//添加下一层的左右节点
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
//深度加1
res++;
}
return res;
}
};