1. Algorithm
226. 翻转二叉树（简单）
描述：
翻转一棵二叉树
示例：
示例：
输入:
4
2 7
1 3 6 9
输出:
4
7 2
9 6 3 1
思路：
- 递归法：翻转一个二叉树，就是把根节点的左子树翻转一下，同样的把右子树翻转一下，再交换左右子树就可以了。
- 迭代法：类似广度优先遍历的方式，使用队列存储尚未交换的节点，每次从队列取出一个结点，交互其左右子结点，直到队列为空。
class Solution {
public TreeNode invertTreeRecursively(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTreeRecursively(root.left);
invertTreeRecursively(root.right);
return root;
}
public TreeNode invertTreeIteratively(TreeNode root) {
if (root == null) {
return null;
}
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
while (list.isEmpty()) {
TreeNode current = list.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
if (current.left != null) {
list.add(current.left);
}
if (current.right != null) {
list.add(current.right);
}
}
return root;
}
}
分析：
递归和迭代法一样：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
326. 3 的幂（简单）
描述：
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例：
输入: 27
输出: true
思路：
- 解法一：累乘法
- 解法二：3的幂次质因子只有3，而整数范围内的3的幂次最大是1162261467
解法：
class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
if (n == 1) {
return true;
}
long m = 1;
while (m < n) {
m *= 3;
if (m == n) {
return true;
}
}
return false;
}
public boolean isPowerOfThree2(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
分析：
解法一：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
解法二：
- 时间复杂度：O(1)
- 空间复杂度：O(1)
2. Review
Goodbye, Object Oriented Programming 再见，面向对象编程
作者是个有着多年经验的老程序员，他毫不留情地指出了面向对象编程的问题，分别从封装、继承和多态这三大支柱来阐述。
- 继承最大的好处就是复用。但是出现了「猴子香蕉丛林」问题，我只想要一根香蕉，得到的却是香蕉丛林。钻石问题，继承关系的结构图就像钻石一样，这样容易造成调用混乱。还有基类问题，子类不知道基类的实现，从而引发操作错误。解决办法就是用组合替代继承，原意是包含和委托。
- 封装使得对象保证内部的变量受保护，然而它却带来了一下问题。引用问题，给构造方法传参时，对象存在多个应用，这样对象就不安全了。解决办法是对象深拷贝，但不是所有对象都支持克隆。
- 面向对象编程不需要多态，它完全可以基于接口来实现。
最后作者告别了面向对象编程，转向函数式编程。
虽然作者举出这么多 OOP 的问题，但是面向对象的思想依然非常流行。软件开发没有银弹，能够实现功能、解决问题的思想都是值得采用的。
3. Tip
日常的琐事都用软件记录，比如有道云笔记、滴答清单、LastPass。大脑是用来思考的，不是用来记东西的，它充当的更多是 CPU 的角色，而不是硬盘。所以，让大脑轻松一下，用工具记录吧。
4. Share
关于线程和I/O模型的极简知识 主要讲述了线程和 I/O 模型的演化历史，问题驱动模型的演化，每种模型都有各自的使用场景。
