万恶的算法作业，要找寻一条边是否在MST中，看似简单，却暗藏玄机，因为一个graph可能不止有一个MST，用Kruskal 算法找到MST固然简单，但找到所有MST似乎就只能用Prim了。不想删掉我辛辛苦苦写的Kruskal算法，便写了这篇文章作为总结。

I encounter this ‘cut and paste’ in my algorithm course, so I searched some information to and found this explaination is good.

这里解释的很好，简单来说，当你想用证明一些算法（大多数情况是动态规划和贪心算法）的正确性时就可以利用矛盾法contradiction和复制粘贴大法cut and paste。因为动态规划或贪心算法都是建立在取最优结果的基础上完成下一步的计算，所以你需要假设我们其中某一步不采用前面的最优结果也可以达到最优的效果，那我们就先cut掉某一步的最优结果，将次优结果paste上去，从而进行推导，得到我们想要的contradiction就大功告成证明成功。

随便写写，反正也没人看。

Rewrite it again during a mock interview. Then I found myself is just a small potato. So write it down to record some mistakes and weakness.

Question: here

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Question: here

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
简而言之，判断过几天天气才能回暖。

Question: here

A binary tree is univalued if every node in the tree has the same value.
Return true if and only if the given tree is univalued.
简而言之，判断问二叉树的每个节点的值是不是都是一样的。

Example:

Input: [1,1,1,1,1,null,1]
Output: true
这题和上次的100很像，但100是比较两个二叉树的，这题是比较自身的值是否一致。所以大致思路会延续上次100，但会有细微不同。

Question: here

Given a binary tree, return the preorder traversal of its nodes’ values.
简而言之，用前序输出二叉树，至于什么是前序preorder，中序inorder和后序postorder，click here

Example:

Input: [1,null,2,3]
  1
   \
    2
   /
  3
Output: [1,2,3]

这一题用递归很简单，遍历就行，但因为遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack空间或者用户自定义的stack），那但如何使空间复杂度为O（1）呢？

This problem is very simple to use recursion, traversal all of them. but because there are two common methods for traversal: one is recursive, and the other is iterative version using stack implementation (stack + iterative). These two methods are both O (n) space complexity (recursion itself occupies stack space or user-defined stack), but how to make the space complexity O (1)?

到不了的都叫做远方，回不去的名字叫家乡