每日一道 LeetCode (22)：二叉树的最大深度

每天 3 分钟，走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

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<TreeNode> queue = new LinkedList<TreeNode>();
    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;
}