1. 首页
  2. LeetCode

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

每日一道 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;
}

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

代码很短,总共就两行,如果要让我讲清楚这两行,属实有点强人所难。

所以,一切看缘分吧,懂就是懂了。

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

第二种方法:迭代

迭代说白了就是循环,整体思路会比递归好理解很多,当然,这种方案代码也会比递归多很多。

首先还是先定义一个队列(好像截止目前,所有遇到二叉树进行迭代都是要先搞一个队列),把我们的二叉树放进去,然后开始第一个大循环,直到我们的队列里面为空结束。

注意哦,我们放在队列里面的是当前层的所有节点,接下来我们在大循环里面再做一个小循环,这个小循环的作用是遍历当前层所有节点,看看这些节点的下一层还有没有新的节点,如果还有就拿出来放到队列里面,没有的话就接着下一次循环。

这解释的够清楚了吧,下面是代码:

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;
}

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

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code