LeetCode|LeetCode 104. 二叉树的最大深度
104. 二叉树的最大深度
给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明:
- 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7],3
/ \
920
/\
157
返回它的最大深度 3 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
- 创建二叉搜索树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
- 1. 递归法
思路:
- 递归终止条件为当前节点为 null
- 依次递归求出根节点的左右子树的高度
- 左右子树高度最大值在加上根节点(+1)即为整个二叉树的高度
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
复杂度分析:
- 时间复杂度:O(n), 需要依次遍历所有节点
- 空间复杂度:O(n), 使用了递归,最坏情况下栈中需要存放 h 个方法调用,h 为二叉树的高度
- 2. 迭代法
思路:使用队列进行层序遍历
- 创建一个队列,将根节点添加进队列中
- 遍历该队列,每次将高度 height++,获取队列的大小,取出队首的元素,依次将其左右节点加入队列中,
- 返回高度 height 即可
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue queue = new LinkedList<>();
queue.add(root);
int height = 0;
while (!queue.isEmpty()) {
height++;
int size = queue.size();
while (size > 0) {
TreeNode cur = queue.poll();
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
size--;
}
}
return height;
}
【LeetCode|LeetCode 104. 二叉树的最大深度】复杂度分析:
- 时间复杂度:O(n), 需要遍历每个节点元素
- 空间复杂度:O(n), 由于使用了队列,队列大小为节点数量
- 源码
- 我会每天更新新的算法,并尽可能尝试不同解法,如果发现问题请指正
- Github
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 数据结构和算法|LeetCode 的正确使用方式