Dimple在左耳听风ARTS打卡（十八）

程序员小跃

发布于 2019-12-27 15:01:09

3140

发布于 2019-12-27 15:01:09

文章被收录于专栏：程序员小跃程序员小跃程序员小跃

21天写作课在上周日已经结束了，21天不是结束，而是一个新的开始。所以，在往后的日子里，我还是会继续通过学到的知识，来更好地写文章。

同时，这周一开始又回到了我熟悉的节奏，会继续把之前落下的关于设计模式的系列更新完，最后几章了，坚持就是胜利。因为是参考书中的内容，所以后面有些并不会和网上部分大神写的那么详细，我会尽量做到更好，感谢大家的支持。

好啦，唠嗑结束，开启今天的打卡之旅。

Algorithm LeetCode算法

二叉树的最大深度 (https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)

题目描述：给定一个二叉树，找出其最大深度。

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

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

示例 1：

给定二叉树 [3,9,20,null,null,15,7]，

输入:

    3
   / \
  9  20
    /  \
   15   7 

输出: 

返回它的最大深度 3

今天我们继续来看二叉树相关的题目，此次是计算二叉树的最大深度，所以做二叉树的前提，你还是需要知道二叉树是什么东西，才能更好地去理解何为深度。

首先，给出我们将要使用的树的结点TreeNode的定义，还是和上次一样，上次我没具体说明白，可能有些读者不知道如何去创建一个二叉树，在这里我补充一个简要的说明。

TreeNode 分为左结点和右结点，每个结点又可以分成N个子结点，所以左右的都是用了TreeNode对象来表示，要定义具体的值，那就用到了val数值，把你需要放入的该节点的值就好了。

比如节点根是3，那就建一个 TreeNode treeNode = new TreeNode(3); 即可，需要有左子结点，则只要treeNode.left = new TreeNode(9);即可，同理继续创建右结点，以及更多的子结点。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
}

方法一：递归

直观的方法是通过递归来解决问题。在这里，我们用了DFS（深度优先搜索）策略的示例。具体代码如下：

public class MaxDepth {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.right = new TreeNode(7);
        int result = maxDepth(treeNode);
        System.out.println(result);
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int result = Math.max(left, right) + 1;
        return result;

    }
}

复杂度分析

时间复杂度：我们每个结点只访问一次，因此时间复杂度为O(N)，其中N是结点的数量。
空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归会被调用N次（树的高度），因此保持调用栈的存储将是O(N)。但是在最好的情况下（树是完全平衡的），树的高度将是log(N)。因此，在这种情况下的空间复杂度将是O(log(N))。

方法二：迭代

我们还可以通过在栈的帮助下将上面的递归转换为迭代，具体的可以去看官方提供的答案噢，在这里就不再赘述啦。

官方地址：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/

Review 阅读并点评至少一篇英文文章

Let’s Speed Up your Gradle Build (https://medium.com/mindorks/lets-speed-up-your-gradle-build-6c0e401883e2)

上篇文章和大家聊到我在掘金上发现的一位翻译Android文章的大佬，叫【驻坑大使】，并且翻译的文章是如何提高Android项目的构建速度。这次，我又从他的资源库里找到一篇姐妹篇，叫《让我们加快你的Gradle构建》。

文章列举了11个要点:

Always use latest android Gradle Plugin
If you are using command line to build ,Avoid Legacy Multidex
Disable Multiple apk for developments
Including Minimal Resources
Disable PNG Crunching
Instant RUN
Use Crashlytics right
Don’t use dynamic dependency version
In gradle.properties file change the memory assigned for JVM according to app requirements.
Enable gradle caching
Multi Module Project

作为Android开发，Gradle构建确实是一大通病，每次构建一个大的项目，都需要泡杯咖啡来，所以能提高构建速度，肯定都是我们喜欢看到的结果。感谢【驻坑大叔】给我们优质的资源，让我也学习了两篇，有了更好的认识。

有条件的朋友，可以看下原文。要么就去掘金关注下【驻坑大使】，他提供的翻译，让我们的Android开发更上一层楼吧。