leetcode 104. Maximum Depth of Binary Tree 二叉树的最大深度(简单)
一、题目大意
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
920
/\
157返回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路 思路：求二叉树的最大深度问题用深度优先搜索 Depth First Search，递归的完美应用。
【leetcode 104. Maximum Depth of Binary Tree 二叉树的最大深度(简单)】思路二：也可以用层序遍历二叉树，然后计数总层数，即为二叉树的最大深度，需要注意的是while循环中的for循环的写法，一定要将q.size()放在初始化里，而不能放在普快停止的条件中，因为q的大小是随时变化的，所以放在停止条件中会出错。
三、解题方法 3.1 Java实现-递归
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode() {}
*TreeNode(int val) { this.val = val;
}
*TreeNode(int val, TreeNode left, TreeNode right) {
*this.val = val;
*this.left = left;
*this.right = right;
*}
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}3.2 Java实现-层序遍历
public class Solution2 {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int ans = 0;
Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
ans++;
for (int i = q.size();
i > 0;
i--) {
TreeNode t = q.poll();
if (t.left != null) {
q.offer(t.left);
}
if (t.right != null) {
q.offer(t.right);
}
}
}
return ans;
}
} 四、总结小记
- 2022/9/5 做开发没有需求设计那就是无穷灾难的开端
推荐阅读
- LeetCode|LeetCode_二分搜索_中等_540.有序数组中的单一元素
- LeetCode|LeetCode_栈_中等_735.行星碰撞
- LeetCode|LeetCode_双指针_中等_611.有效三角形的个数
- LeetCode|LeetCode算法刷题目录（Java）
- [Leetcode]|[Leetcode] 87. Binary Tree Level Order Traversal II
- LeetCode 题解 | 1. 两数之和 Javascript 版
- 220902_leetcode 21. Merge Two Sorted Lists 合并两个有序链表(简单).md
- leetcode 206. Reverse Linked List 反转链表(简单)
- Leetcode-222题:Count|Leetcode-222题:Count Complete Tree Nodes
- leetcode|【Leetcode】刷题题单记录