【LSP】 LeetCode (22)：二叉树的最大深度

村长发表于 2020-12-5 22:29:25

http://cdn.u1.huluxia.com/g4/M01/5A/7F/rBAAdl9ulqyAe-2oAACt4WdlvYs796.jpg
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树，

3
/ \
920
/\
15 7
返回它的最大深度 3 。

解题思路
经过前两天的训练以及学习，看到这道题的第一个反应应该是这题有两种做法，一种是递归，另一种是迭代。

如果这个都没想到的同学，建议重新看下前面两篇文章，看完以后记得一定要自己手动实现一遍。

毕竟实践出真知。

第一种方法：递归

关于如何递归我就不多说了，这玩意很难讲清楚，更好的方式是自己拿到代码，多 debug 几次，自然就理解了，可能这就是天赋？

public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
http://cdn.u1.huluxia.com/g4/M01/5A/7F/rBAAdl9ulqyAa6j7AABBCLNyF8U299.png
代码很短，总共就两行，如果要让我讲清楚这两行，属实有点强人所难。

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

第二种方法：迭代

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

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

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

这解释的够清楚了吧，下面是代码：

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;
}http://cdn.u1.huluxia.com/g4/M01/5A/7F/rBAAdl9ulqyAMVYEAABBAv0J_K4768.png

无量科技 发表于 2020-12-5 22:38:39

占位编辑

梦影发表于 2020-12-7 14:38:55

看帖要回，回帖才健康，在踩踩，楼主辛苦了！

neige 发表于 2020-12-9 12:31:22

沙发？？？

天镜盗梦 发表于 2020-12-10 12:20:02

楼下的接上

liqiang24 发表于 2020-12-12 10:52:08

传说中的沙发？？？哇卡卡

68079330 发表于 2020-12-12 12:20:25

介是神马？！！

伴我多久 发表于 2020-12-12 13:00:01

在撸一遍。。。

页: [1]

村长黑科技's Archiver

【LSP】 LeetCode (22)：二叉树的最大深度