每日一道 LeetCode (22)：二叉树的最大深度
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：二叉树的最大深度
题目来源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路
经过前两天的训练以及学习，看到这道题的第一个反应应该是这题有两种做法，一种是递归，另一种是迭代。
如果这个都没想到的同学，建议重新看下前面两篇文章，看完以后记得一定要自己手动实现一遍。
毕竟实践出真知。
第一种方法：「递归」
关于如何递归我就不多说了，这玩意很难讲清楚，更好的方式是自己拿到代码，多 debug 几次，自然就理解了，可能这就是天赋？
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
代码很短，总共就两行，如果要让我讲清楚这两行，属实有点强人所难。
所以，一切看缘分吧，懂就是懂了。
第二种方法：「迭代」
迭代说白了就是循环，整体思路会比递归好理解很多，当然，这种方案代码也会比递归多很多。
首先还是先定义一个队列（好像截止目前，所有遇到二叉树进行迭代都是要先搞一个队列），把我们的二叉树放进去，然后开始第一个大循环，直到我们的队列里面为空结束。
注意哦，我们放在队列里面的是当前层的所有节点，接下来我们在大循环里面再做一个小循环，这个小循环的作用是遍历当前层所有节点，看看这些节点的下一层还有没有新的节点，如果还有就拿出来放到队列里面，没有的话就接着下一次循环。
这解释的够清楚了吧，下面是代码：
public int maxDepth_1(TreeNode root) {
if (root == null) return 0;
Queue queue = new LinkedList();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
评论