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

程序员小跃

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

3880

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

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

所谓ARTS：每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第十九期打卡。

在文章开头，想给自己前几天写的一篇文章打个推广，这篇文章是告诉我们如何更好地去做好一件事，那就是不停地给自己做减法减法减法，每次只做好一件事，那就是最重要的事。

该篇文章还上了CSDN的首页推广，给很多小伙伴产生了共鸣，所以也请没看过的读者可以移步去看下哦。《成就更好的自己，就是不停地做减法》

Algorithm LeetCode算法

将有序数组转换为二叉搜索树 (https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/)

题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例 1：

给定有序数组 [-10,-3,0,5,9]

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树

输入:

    0
   / \
  -3  9
  /   /
 -10 5

在介绍解法之前，首先我们先来了解下什么是二叉搜索树。

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树分别为二叉查找树；
没有键值相等的节点

而且，题目中说明了，是一个升序数组，那么在二叉树中中序遍历输出的就是升序数组。

根据中序遍历加前序遍历或者中序遍历后序遍历来还原一棵树。前序（后序）遍历是为了提供根节点。然后我们根据根节点，就可以了递归的生成左右子树了。

因为是平衡二叉树，所以只要把根节点选为数组的中点就好了。找到根节点，然后把数组一分为二，进入递归，就迎刃而解啦。

public static void main(String[] args) {
        int[] nums = {-10,-3,0,5,9};
        TreeNode treeNode = sortedArrayToBST(nums);
        System.out.println(treeNode);
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length);
    }

    public static TreeNode sortedArrayToBST(int[] nums,int start,int end) {
        System.out.println("start = " + start + " end = " + end);
        if (start == end) {
            return null;
        }

        int mid = (start + end) >>> 1;
        System.out.println("mid = " + mid + " start = " + start + " end = " + end);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid);

        System.out.println("start = " + start + " end ====================== " + end);
        System.out.println("mid = " + mid + " end = " + end);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }

当然，这里还有多于一种的解决方案，还有通过栈、通过队列的方式来解决。小编也是参考了课后的优秀题解，所以推荐大家前往https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-24/这里查看。当然，阅读原文处已经把链接加上了，可以直接过去哦。

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

My first experience with Kotlin Native (https://link.juejin.im/?target=https%3A%2F%2Fmedium.com%2F%40champigny.florent%2Fmy-first-experience-with-kotlin-native-988e96f26657)

今天我们来了解下Kotlin，这是一位外国友人在Medium上发表的题为《My first experience with Kotlin Native》。

文章篇幅还是有点长的，让我看的很辛苦。我这个英语水平，真的是太累了，所以，英语学习很重要呢。

作者记录了自己如何成功创建第一个Android和iOS兼容模块，以及如何将其集成到实际应用程序中。

分别是：