【题干】
给定一个二叉树?root
?,返回其最大深度。
二叉树的?最大深度?是指从根节点到最远叶子节点的最长路径上的节点数。
【思路】
还是二叉树经典题,今天写两个解法。
【题解】
dfs
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root==nullptr){
return 0;
}
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
bfs
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
queue<TreeNode*> q;
q.push(root);
int ans = 0;
while (!q.empty()) {
//把当前层拿出来扩展一遍
int cnt = q.size();
while (cnt) {
TreeNode* cur = q.front();
q.pop();
if (cur->left!=nullptr)
q.push(cur->left);
if (cur->right!=nullptr)
q.push(cur->right);
cnt--;
}
//计数
ans++;
}
return ans;
}
};