Dimple在左耳听风ARTS打卡（十七）
所谓ARTS：每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第十七期打卡。
小编文章的阅读量不高，粉丝也不多，所以还是蛮在意读者的感受的。昨天有读者联系我，说我最近文章有点空，尴尬。上次前辈就告诫过我，说我有点走偏了，没想到这么快读者就反馈了，狠狠的给我当头一棒。
所以，接下来的日子，我肯定会时刻保持清醒，更多的专注于Java和Android相关的分享，适当的分享下前辈们觉得不错的工具、文章、独到的见解等等。读者朋友们有什么需求，有什么想法，有什么不爽的，欢迎过来找我吐槽，给我清醒的机会。
Algorithm LeetCode算法
合并二叉树 (https://leetcode-cn.com/problems/merge-two-binary-trees/)
题目描述：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL的节点将直接作为新二叉树的节点。
示例 1：
输入:
Tree 1 Tree 2
1 5
/ \ / \
2 3 3 6
/ \ / / \
4 5 2 1 4
输出:
合并后的树:
6
/ \
5 9
/ \ / \
6 5 1 4
注意: 合并必须从两个树的根节点开始。
小编这次对选题改了下策略，从今天开始，会有目的性的进行选题。前几次的选题，都是按顺序而来，然后是挑选简单的练习下意识。
直到我看了极客时间的《Android开发高手课》上关于Android面试的那节课，老师也提到练习算法是一个很重要的事情，可以对题目进行筛选，把自己认为重要的题先做。
我自己的性格本身就是想按部就班的，也是一根筋的表现，以后还得寻求变通。今天的选题，筛选了网站上的“热题 HOT 100”，而且二叉树也是热点，就顺势写一个呗。
当前题目上，是合并二叉树，那很显然，我们的思路就和描述一样，同一个节点有两个值则进行相加，否则取其一即可。具体的，就看我的解题吧，这个方式是比较好的。
public class MergeTrees {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(1);
t1.left = new TreeNode(2);
t1.right = new TreeNode(3);
t1.left.left = new TreeNode(4);
t1.left.right = new TreeNode(5);
TreeNode t2 = new TreeNode(5);
t2.left = new TreeNode(3);
t2.left.left = new TreeNode(2);
t2.right = new TreeNode(6);
t2.right.left = new TreeNode(1);
t2.right.right = new TreeNode(4);
TreeNode result = mergeTrees(t1, t2);
}
public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
当然啦，这个题目还有第二种解法，使用栈的方式来的。在Leetcode的英文官网，solution下可以看到动态的运行原理图，以及相应的代码和激烈的讨论，大家可以去围观下哦。地址是：(https://leetcode.com/problems/merge-two-binary-trees/solution/)
public static TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
Stack < TreeNode[] > stack = new Stack < > ();
stack.push(new TreeNode[] {t1, t2});
while (!stack.isEmpty()) {
TreeNode[] t = stack.pop();
if (t[0] == null || t[1] == null) {
continue;
}
t[0].val += t[1].val;
if (t[0].left == null) {
t[0].left = t[1].left;
} else {
stack.push(new TreeNode[] {t[0].left, t[1].left});
}
if (t[0].right == null) {
t[0].right = t[1].right;
} else {
stack.push(new TreeNode[] {t[0].right, t[1].right});
}
}
return t1;
}
Review 阅读并点评至少一篇英文文章
How to improve the build speed of your Android projects (https://www.freecodecamp.org/news/how-to-improve-the-build-speed-of-your-android-projects-bd49029d8602/)
前段时间在掘金上关注了一个号主，叫“驻坑大使”，看到有好几篇关于Android的翻译，提起了我的兴趣，上周的那篇翻译，也是从他的资源里找到的。
这礼拜，又看到一篇是关于如何提升Android项目的构建速度的，我觉得也是有必要和大家分享下。
因为做Android开发的都知道，从早期的Eclipse开发，到现在的Android Studio，编译速度一直是个问题。很多时候一个稍微比较大的项目，光编译花费的时间就够你泡一杯咖啡甚至还能喝上几口。
在优化之前，我们可以先记录下优化之前需要的时间，以此来证明这个优化是否真的对我们是有效的。关于如何记录，文中的But first页签下已经告诉我们了哦。
紧接着就是三大步骤，如下：
Step #1: Update your tooling
Step #2: Update your configurations
Step #3: Gradle Properties
解释起来分别是，更新你的开发工具，更新你的配置，更新Gradle，然后就可以去看看是不是溜的飞起啦。
还有这个网站也是我新发现的一个网站，感觉还蛮不错的，感兴趣的朋友可以再去看看其他的文章。
Tip 一个技术技巧
昨天在一个技术群里，聊了下微服务相关的话题，忽然想起前段时间学习微服务的时候，CAP定理让我印象深刻，这里同大家分享出来。
CAP定理
CAP定理是分布式系统设计中最基础，也是最为关键的理论。它指出，分布式数据存储不可能同事满足以下三个条件。
- 一致性（Consistency）：每次读取要么获得最近写入的数据，要么获得一个错误
- 可用性（Availability）：每次请求都能获得一个（非错误）响应，但不保证返回的是最新写入的数据
- 分区容忍（Partition tolerance）：尽管任意数量的消息被节点间的网格丢失（或延迟），系统仍继续运行
- CA（consistency + availability），这样的系统关注一致性和可用性，它需要非常严格的全体一致性。比如“两阶段提交”。
- CP（consistency + partition tolerance），这样的系统关注一致性和分区容忍性。塔关注的是系统里大多数人的一致性协议，比如：Paxos算法（Quorum类的算法）
- AP（availability + partition tolreance），这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。Dynamo就是这样的系统。