kitt blog (欢迎留言，最近刷的题目放到github上了)

递归方法, 判断左右子树是否对称: 1)左右子树的根节点都为空或者val相同, 2)左子树的左子树与右子树的右子树对称, 3)左子树的右子树与右子树的左子树对称。

和Permutation那道题目差不多，也是递归，不过要去重。先排序，再利用prevNum变量区分是否重复。

一开始我用被除数一次一次地减除数，这样太慢了，遇到被除数为2147483648除数为1的情况就挂了。可以用被除数不断地减除数的1倍、2倍、4倍、8倍...这样就快了。使用位运算，被除数与除数同号时商为正，异号时商为负。

Use a stack.

这题还真是奇葩啊

先对所有intervals按start值排序, 然后遍历, 如果当前Interval.start <= 已merged的大的Interval.end, 则扩展已merged的大的Interval.end。

BST中序遍历就是一个sorted list, 要求O(1) space, 经1楼提醒, 用first, second两个变量记录可能交换的节点即可。如果只有一个降序对(如20, 10, 30, 40, 50), 用first, second记录。如果有两个降序对(如10, 40, 30, 20, 50或50, 20, 30, 40, 10), 用第二个降序对中小的数更新second。while循环中19~23行换成"print root.val"就是非递归的中序遍历。

The result of BST inorder traversal is a sorted list. This problem requires O(1) space, according to the first comment below, only two variables (first, second) are enough to record nodes to be exchanged. If there's only one descending order pair (e.g. 20, 10, 30, 40, 50), use first & second to record it. If there are two descending order pairs (e.g. 10, 40, 30, 20, 50 or 50, 20, 30, 40, 10), use the smaller number in second pair to update second. If we change line 19-23 in while loop to "print root.val", then it's non-recursive inorder traversal of binary tree.

用dictionary, get item的平均时间复杂度为O(1), 可以把key设为list中的数, value用于标记是否访问过。遍历所有的key, 不断找寻其+1和-1得到的值是否在dictionary中, 记下最长的连续序列长度。

父节点把已有的值传给子节点, 子节点把这个值乘以10再加上自身的值。

记录最远能到达的范围, 每次在这个范围内搜, 找出下一跳的最远范围, 更新最远范围和跳数。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isBalanced(self, root):
        return self.check(root)[1]
        
    # @param root, a tree node
    # @return a tuple (int height, bool isBalanced)
    def check(self, root):
        if root == None: return (0, True)
        LH, LisB = self.check(root.left)
        RH, RisB = self.check(root.right)
        return ( max(LH, RH) + 1, LisB and RisB and abs(LH - RH) <= 1 )

左右子树只存在一个时不能返回0, 而是要沿着那个子树继续找下去。

递归, 对于[start, end]范围内的每个节点, 产生所有可能的左、右子树, 再产生(#左子树 x #右子树)棵树, 返回所有的root nodes。gen函数返回一个list of root nodes, 每个root node所表示的树是由[start, end]这个范围内的数构成的BST。

动态规划, 节点数为0算一种情况, 即null。左、右子树节点共n-1个。左子树节点数从0走到n-1, 当左子树节点数为k时, 所有可能情况有dp[k] * dp[n-1-k]种。

用一个变量记录最大可到达的位置, 每次在这个位置之前找。

key = sorted word, value = [word1, word2, word3, ...]

看了这个解法, 犀利！首先转成求A和B数组中第k小的数的问题, 然后用k/2在A和B中分别找。比如k = 6, 分别看A和B中的第3个数, 已知 A1 < A2 < A3 < A4 < A5... 和 B1 < B2 < B3 < B4 < B5..., 如果A3 <＝ B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1, 三个数小于A2, 四个数小于A3。B3至少大于5个数, 所以第6小的数有可能是B1 (A1 < A2 < A3 < A4 < A5 < B1), 有可能是B2 (A1 < A2 < A3 < B1 < A4 < B2), 有可能是B3 (A1 < A2 < A3 < B1 < B2 < B3)。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。每次都假设A的元素个数少, pa = min(k/2, lenA)的结果可能导致k == 1或A空, 这两种情况都是终止条件。 

使用两个指针