情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
方案：计算两个节点到根节点的深度相加。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
方案：计算两个节点到子树根节点的深度相加
利用空间换时间。使用临时变量保存之前计算好的值。
分配饼干问题？每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。Input:[1,2], [1,2,3]。Output: 2
贪心算法。对饼干、孩子满足度进行排序。然后先用小饼干给满足度低的孩子。不造成浪费。
public static int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 计算左子树的深度
int left = treeDepth(root.left);
// 计算右子树的深度
int right = treeDepth(root.right);
// 树root的深度=路径最长的子树深度 + 1
return left >= right ? (left + 1) : (right + 1);
}
- 借助一个队列，先把根节点入队，每打印一个节点的值时，也就是打印队列头的节点时，
- 都会把它的的左右孩子入队，并且把该节点出队。直到队列为空。
借助一个队列和一个栈，方法和打印层遍历类似，区别在于隔层利用栈来逆序遍历。
- 可以利用栈逆序拼接。
- 利用三个指针引用，一次性遍历反转，在每次反转两个节点的时候，都需要保存下一个节点，以免丢失原链表。
复制成 1->1'->2->2'->3->3' 的链表，然后再拆分出来 1'->2'->3'
第一种做法：先将链表拆分成奇数的链表，和偶数的链表，然后翻转偶数的链表，在合并两个链表。
不支持随机访问，查找的时间复杂度是O(n)
准备两个指针，一个步长为1，一个步长为2，当遍历到的指针相同时，则判定出现环
最小堆算法
遍历数组，从第一个大于0的数字开始累加，保存最大值，如果累加后的值小于等于0的话，就抛这一下标，
从下一个下标开始累积，如果超过之前的最大值的话就进行替换。使用sum和max变量进行操作
将所有数字放入数字对应下标的数组，有N个相同的数字，该下标的值就为N。 从i下标开始遍历，S-i下标对应值>0的话，就找到组合。 i=s-i的话，做特殊处理。
所有值进行异或运算。最后的值再和0异或，得到原来的值。
先找出旋转90度，下标的变换规律。 然后从外圈向内圈旋转变换。
| 排序算法 | 时间复杂度 |
|---|---|
| 冒泡排序 | O(n2) |
| 选择排序 | O(n2) |
| 插入排序 | O(n2) |
| 希尔排序 | O(n1.5) |
| 快速排序 | O(N*logN) |
| 归并排序 | O(N*logN) |
| 堆排序 | O(N*logN) |
| 基数排序 | O(d(n+r)) |
基本思想：（分治）
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
- 利用数组建立一个大根堆（父亲比孩子的值大）；
- 把堆顶元素和堆尾元素互换；
- 把堆（无序区）的尺寸缩小1，并调用siftDown(arr, 0,len-1)从新的堆顶元素开始进行堆调整；
- 重复步骤，直到堆的大小为1；
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，
取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
- 插入排序，然后找到中间位置。
- 借鉴快排的思想，随机取一个数，大于它的排左边，小于它的排右边。检测所选数字是否位于数组中间。
是的话就返回，不是的话，小于数组中间位置就对右边递归，大于数组中间位置就对左边递归。
- 堆可以被看成是一棵完全二叉树树，如：堆排序。
- 一种先进后出的数据结构。
PriorityQueue是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。
在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值，因为
他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue不是线程安全的，
入队和出队的时间复杂度是O(log(n))。
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，
进行运算，运算结果进栈，一直到最终获得结果。
对于表达式计算非常方便
重写LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int MAX_CACHE_SIZE;
public LRUCache2(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
}
声明一个大小为10000000的数组，每次随机出来的数i，都去数组下标i-1的位置看是否为0，如果为0的话，
写入这个数字，并记录数组的真实大小，等数组的真实大小为10000000的时候，停止随机。
同时遍历两个数组，每次对比两个数组当前坐标的值哪个小，小的存入新的数组，数组下表往后移一位，
大的那边坐标不变，继续下次大小对比。依次循环。
每次交换头尾的值，并坐标向中间靠拢。
前序递归：
public void preOrderTraverse1(TreeNode root) {
if (root != null) {
System.out.print(root.val + "->");
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
}
}
前序非递归：
public void preOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.empty()) {
if (node != null) {
System.out.print(node.val + "->");
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
node = tem.right;
}
}
}
中序递归：
public void inOrderTraverse(TreeNode root) {
if (root != null) {
inOrderTraverse(root.left);
System.out.print(root.val + "->");
inOrderTraverse(root.right);
}
}
中序非递归：
public void inOrderTraverse(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
System.out.print(tem.val + "->");
node = tem.right;
}
}
}
后序递归：
public void postOrderTraverse(TreeNode root) {
if (root != null) {
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.val + "->");
}
}
后序非递归：
public void postOrderTraverse(TreeNode root) {
TreeNode cur, pre = null;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
cur = stack.peek();
if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
System.out.print(cur.val + "->");
stack.pop();
pre = cur;
} else {
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
}
}
层次遍历：
public void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + "->");
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
深度优先算法:利用栈实现 广度优先算法：利用队列来实现
利用栈与后缀表达式利于计算机方便计算
按权重将节点分布在一条右子树上，使得前缀不重复
- 平衡二叉树，左右高度之差不超过1，Add/delete可能造成高度>1，此时要旋转，维持平衡状态，
- 避免二叉树退化为链表，让Add/Delete时间复杂度但控制在O(log2N)，旋转算法2个方法，1是求树的高度，
- 2是求2个高度最大值，1个空树高度为-1，只有1个根节点的树的高度为0，以后每一层+1，平衡树任意节点
- 最多有2个儿子，因此高度不平衡时，此节点的2棵子树高度差为2。例如单旋转，双旋转，插入等。红黑树放弃
- 完全平衡，追求大致平衡，保证每次插入最多要3次旋转就能平衡。
利用bit数组，通过不同的哈希函数定位数组中的坐标。 如果都存在的话，代表存在。有一定误判率。
数组查找是O(1)，删除或者新增是O(N)
链表查找是O(N)，删除或者新增是O(1)
递归遍历和循环遍历
MD5和SHA256 1.保护密码。 2.防止文件篡改 3.数字签名（对整段内容加密比较费性能，所以只对哈希值进行加密） 4.文件秒传
可以使用类似选择排序，类似快排，类似最大堆的算法
利用原子数字，对三取余，打印对应的abc。或者利用三个condition进行唤醒。
分治，加最小堆
1b是8比特。
1kb是8192比特
大概12mb内存可以代表1亿数字的比特位
利用哈希来判断
准备一个大数组。依次放入数组。数字出现n次，对应下标值就为n，完成之后，遍历数组。
当累加数值为1亿时，对应下标即为中位数。时间复杂度即为O(N)
累加每个位置上的bit位%3 即为不重复的数字的bit位
在原数组中对调首尾对称的位置
log2N 优势是 性能平均
递归更换左右子树即可
准备两个指针，初始指向头结点， 1号指针先走n步，然后2号指针开始走，当1号指针走到尾节点时，2号指针即为倒数第N个数据。
依次遍历每个有序数组（假设数组从大到小），对比这200个数字，最大的放入top20数组，重复20次该操作，即可获得top20数组
一个步长为1的游标，一个步长为2的游标，当步长为2的游标到达链表末尾时，步长为1的游标即中间元素
分割，或者流式读取，然后利用一个大小为10的小根堆。
或者分成100份，每份计算最大的10个数字，最后对比这个1000个数字
先划分成多个小文件，送进内存排序，然后再采用多路归并排序。
快排等算法。
先用遍历一次十万单词，放入hashmap中，key为单词，value为次数。然后再遍历hashmap，放入最小堆，可以使用priorityqueue或者大小为10的数组也行