创建树
1. Preorder + Inorder --> Binary Tree
[1]
/ \
[5] [4]
/ \ \
[2] [3] [6]
/
[7]
In-order: 【(2,5,3) 1 (4,7,6)】
Pre-order: 【1 (5,2,3) (4,6,7)】
key: 递归 + 传入时候, inorder + preorder对应left, right的范围
Time: O(N^2), 最坏的情况是，tree is left skewed. Example Preorder and Inorder traversals for worst case are {A, B, C, D} and {D, C, B, A}. For each level, traverse all node in in-order array, O(n), and left skewed tree has N level. Therefore, n^2 is time complexity.
pre-order的第一个永远是root, 剩下的都是left and right subtree.
所以问题转换成how to divide the rest of treenodes into right subtree and left subtree.
这个时候，就需要用Inorder的序列来确定left subtree的长度了.
可以通过在inorder里面找root的值来判断left subtree的长度.
知道长度之后，也就知道了怎么去divide了. 然后递归的时候，left subtree传入相应的preorder and inorder的范围就可以了.
2. Inorder + Postorder --> Binary Tree
key: 熟悉的配方
3. Unique Binary Search Trees
key: 数个数，用dp
有点类似permutation, 所以这是有规律的。
n = 0
n = 1
1
n = 2
1 2
\ /
2 1
n = 3
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
用n = 3来举例：
根节点可以为{1， 2， 3}中的任意一个。
如以1为节点，则left subtree只能有0个节点，而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为：f(0) * f(2) = 2
以2为节点，则left subtree只能为1，right subtree只能为2：f(1) * f(1) = 1
以3为节点，则left subtree有1, 2两个节点，right subtree有0个节点：f(2)*f(0) = 2
所以规律为：
f(n) = f(0) * f(n - 1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)
这个思路有点类似于Inorder，决定了中间的root的之后，看两边的数字有多少种组合。
4. Unique Binary Search Trees II
key: recursion + list and queue can store null object
要求生成所有的unique BST，类似combination/permutation的题目，可以递归构造。
1. 根节点可以任取min ~ max (例如min = 1, max = n)，假如取定为i。
2. 则left subtree由min ~ i-1组成，假设可以有L种可能。right subtree由i+1 ~ max组成，假设有R种可能。生成所有可能的left/right subtree。
3 对于每个生成的left subtree/right subtree组合<T_left(p), T_right(q)>，p = 1...L，q = 1...R，添加上根节点i而组成一颗新树。
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<TreeNode>();
return build(1, n);//1...n
}
private List<TreeNode> build(int left, int right) {
List<TreeNode> list = new LinkedList<TreeNode>();
//key: list and queue can store null, size = 1
if (left > right) {
list.add(null);
return list;
}
for (int i = left; i <= right; i++) {
List<TreeNode> leftTree = build(left, i - 1);
List<TreeNode> rightTree = build(i + 1, right);
//base case: leaf node的两个list都储存了一个null
for (int a = 0; a < leftTree.size(); a++) {
for (int b = 0; b < rightTree.size(); b++) {
TreeNode root = new TreeNode(i);
root.left = leftTree.get(a);
root.right = rightTree.get(b);
list.add(root);
}
}
}
return list;
}
}
Different Ways to Add Parentheses
Like a binary tree, root and all internal nodes are operators; leaves are number
map(string, List<number result>)
class Solution {
//like a binary tree. root and all internal nodes are operator
//leaves are num
//construct different binary tree
public List<Integer> diffWaysToCompute(String input) {
Map<String, List<Integer>> memo = new HashMap<String, List<Integer>>();
constructTree(input, memo);
return memo.get(input);
}
private List<Integer> constructTree(String input, Map<String, List<Integer>> memo) {
List<Integer> res = new LinkedList<Integer>();
for (int i = 0; i < input.length(); i++) {
char curr = input.charAt(i);
if (curr == '+' || curr == '-' || curr == '*') {
String leftPart = input.substring(0, i);
List<Integer> left = memo.containsKey(leftPart) ? memo.get(leftPart) : constructTree(leftPart, memo);
memo.put(leftPart, left);
String rightPart = input.substring(i + 1);
List<Integer> right = memo.containsKey(rightPart) ? memo.get(rightPart) : constructTree(rightPart, memo);
memo.put(rightPart, right);
for (int l: left) {
for (int r: right) {
if (curr == '+') res.add(l + r);
else if (curr == '-') res.add(l - r);
else res.add(l * r);
}
}
}
}
// base case. e.g."11"
if (res.size() == 0) res.add(Integer.parseInt(input));
memo.put(input, res);
return res;
}
}