1. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
思路：和 Unique Binary Search Trees II 不同，只是需要计算总共的数量，可以利用dp来解决。从1~n选择i作为root，那么1到i-1构成其左子树，i+1到n构成其右子树。作如下定义，
G(n): the number of unique BST for a sequence of length n.
F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
从以上定义，可得
G(n) = F(1, n) + F(2, n) + ... + F(n, n). 并且G(0)=1, G(1)=1. 即空树和只有一个节点的情况。对于dp，要解决的问题是能分成若干个相同的子问题，并且计算有重复的情形。以 [1, 2, 3, 4, 5, 6, 7] 为例子，要计算的是G(7)，如果以3为根，要计算F(3,7)。[1,2]构成左子树，[4,5,6,7]构成右子树。对于[1,2]，其实就是计算G(2)，而对于[4,5,6,7]，可以将其等同于计算G(4)，即F(3,7) = G(2) * G(4)。因此有下面等式
F(i, n) = G(i-1) * G(n-i) 1 <= i <= n 结合上面的公式可得出
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 所以从低向上计算，即从G(0)，G(1)开始一直计算出G(n)即可。
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
2. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
思路：层次遍历二叉树，没什么好说的，主要是掌握队列的用法。
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}
}
关于java中队列的用法可以参考这篇博文：https://www.cnblogs.com/samjustin/p/5785078.html
3. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
思路：基于上个题目的改进，本来以为改下上题的代码，判断每层层号的奇偶，再逆置，这样做的确可以解题，但是太过繁琐。还是参考了下答案。使用递归思路求解，对于层次遍历来说，每一层的遍历，都是逻辑相同，参数不同。关键是怎么在这个递归中寻找终止条件，以及一层层向下递归时固定的参数变化规律。
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level)
{
if(curr == null) return; // 没有下层了，递归就往上层返回
if(sol.size() <= level) // 当递归发现还有下层的话，就为这层新建个List，并加入到sol中
{
List<Integer> newLevel = new LinkedList<>();
sol.add(newLevel);
}
List<Integer> collection = sol.get(level); // 这里根据层号取List，所以即使两个从上到下的递归路径不同，但是相同层取到的还是相同的List
if(level % 2 == 0) collection.add(curr.val); // 根据层号奇偶判断这层的List在加入元素时是正序还是逆序
else collection.add(0, curr.val); // 学到了
travel(curr.left, sol, level + 1); // 往下层左子树递归
travel(curr.right, sol, level + 1); // 往下层右子树递归
}
}
上面的基本递归思路是利用到DFS，整个过程每层的元素不是一层层遍历完的，而是每递归到一个底层，从这层往上的所有层所对应的List都添加了在这层遍历到的元素，并且根据层号的奇偶决定是往后插还是往前插，这样来实现顺序和倒序的遍历，这也为层次遍历提供了一种递归实现的思路。注意上面的 collection.add(0, curr.val) 方法，将值插入指定位置，原来位置上的值会依次往后移。