二叉树的最大深度
# 📃 题目描述
题目链接:104. 二叉树的最大深度 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
# 🔔 解题思路
# 迭代法
最容易想到的,就是利用层次遍历,每遍历一层就将深度 +1:
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
// 根节点入队
queue.offer(root);
// 树的深度
int depth = 0;
while (!queue.isEmpty()) {
// 当前层节点的个数
int size = queue.size();
depth ++;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
return depth;
}
}
# 递归法
先求出左右子树的高度,然后再计算根节点所在树的高度,典型的后续遍历,左右根
class Solution {
public int maxDepth(TreeNode root) {
// 递归出口
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
// 左子树的高度
int leftDepth = maxDepth2(root.left);
// 右子树的高度
int rightDepth = maxDepth2(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10