原题
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
思路一 – DFS
代码
class Solution {
public:
int maxDepth(TreeNode* u) {
if (u == nullptr) return 0;
if (u->left == nullptr && u->right == nullptr) return 1;
int ldep = 0, rdep = 0;
if (u->left != nullptr) ldep = maxDepth(u->left) + 1;
if (u->right != nullptr) rdep = maxDepth(u->right) + 1;
return max(ldep, rdep);
}
};
复杂度分析
时间复杂度:O(n) 树节点的个数
空间复杂度:O(h) h 树的最大高度
思路二 – 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()) {
++ans;
int l = q.size();
while (l--) {
auto node = q.front();
q.pop();
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
}
return ans;
}
};
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) 二叉树的叶子节点上限为 n / 2,故空间复杂度的上限为O(n)
参考
[1]. LeetCode 原题. https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-104-maximum-depth-of-binary-tree/