Java 带泛型的 Collections 确实是可以放 null 的， 比如 Queue, List...
这题考察的是 Binary Tree 和 BST 的结构，比较容易想到的思路是画几个 base case 出来然后开始往上加新的 node，不过容易陷进去，开始去抠 detail 去开始想如何添加新点而不违反 BST 性质。
上面那个思路只对了一半，因为 F(n) 是和之前的解 F(n - a) 有联系的，但是思考方向错了。
正确的思路是，给定 n 个 node 之后，直接看 inorder 数组【1, 2, 3, 4 .. n-1, n】
那么选任意位置的元素为 root，都可以建出来一个 valid BST，左子树为 index 左边的 subarray，右子树为 index 右边的 subarray.
于是这就变成了一个利用递归结构的“组合”问题了，解的数量左右相乘。inorder 是 BST 的灵魂啊。
下面是第一次写 AC 的代码，有点粗糙。
public class Solution {
public int numTrees(int n) {
if(n <= 2) return n;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
for(int j = 0; j <= i - 1; j++){
int leftCount = j;
int rightCount = i - 1 - j;
dp[i] += dp[leftCount] * dp[rightCount];
}
}
return dp[n];
}
}
顺着上题的思路，这题也很好做。让我比较惊讶的是改好了拼写之后居然一次提交直接 AC....
public class Solution {
public List<TreeNode> generateTrees(int n) {
return build(1, n);
}
private List<TreeNode> build(int left, int right){
List<TreeNode> list = new ArrayList<TreeNode>();
if(left > right){
return list;
}
if(left == right){
list.add(new TreeNode(left));
return list;
}
for(int i = left + 1; i <= right - 1; i++){
List<TreeNode> leftTree = build(left, i - 1);
List<TreeNode> rightTree = build(i + 1, right);
for(int leftPtr = 0; leftPtr < leftTree.size(); leftPtr++){
for(int rightPtr = 0; rightPtr < rightTree.size(); rightPtr++){
TreeNode root = new TreeNode(i);
root.left = leftTree.get(leftPtr);
root.right = rightTree.get(rightPtr);
list.add(root);
}
}
}
List<TreeNode> rightTree = build(left + 1, right);
for(int i = 0; i < rightTree.size(); i++){
TreeNode root = new TreeNode(left);
root.right = rightTree.get(i);
list.add(root);
}
List<TreeNode> leftTree = build(left, right - 1);
for(int i = 0; i < leftTree.size(); i++){
TreeNode root = new TreeNode(right);
root.left = leftTree.get(i);
list.add(root);
}
return list;
}
}
参考了下论坛，同一个思路，比较简洁的写法是
Java 带泛型的 Collections 确实是可以放 null 的， 比如 Queue, List...
在这题里最两边的情况下，list 里直接加个 null 作为 node 用就可以让代码变得非常简洁。
public class Solution {
public List<TreeNode> generateTrees(int n) {
return n > 0 ? build(1, n) : new ArrayList<TreeNode>();
}
private List<TreeNode> build(int left, int right){
List<TreeNode> list = new ArrayList<TreeNode>();
for(int i = left; i <= right; i++){
List<TreeNode> leftTree = build(left, i - 1);
List<TreeNode> rightTree = build(i + 1, right);
for(int leftPtr = 0; leftPtr < leftTree.size(); leftPtr++){
for(int rightPtr = 0; rightPtr < rightTree.size(); rightPtr++){
TreeNode root = new TreeNode(i);
root.left = leftTree.get(leftPtr);
root.right = rightTree.get(rightPtr);
list.add(root);
}
}
}
if(list.size() == 0) list.add(null);
return list;
}
}
比较简单的问题，唯一需要考虑的是状态的不连续性；最接近的点可能是 BST 一直往下走的 node，也可能是前面某个 node.
用区间的思想去理解的话，每个 node 都有自己的 valid 区间，区间与区间是重合的。对于给定 target，我们先要找到 target 是什么，然后决定 target 到底靠近重合区间的左边还是右边。
public class Solution {
public int closestValue(TreeNode root, double target) {
return find(root, target, null);
}
public int find(TreeNode root, double target, Integer prev){
if(root == null) return -1; // Error
if(prev == null) prev = root.val;
prev = (Math.abs(root.val - target) < Math.abs(prev - target)) ? root.val: prev;
if(root.left != null && target < root.val){
return find(root.left, target, prev);
}
if(root.right != null && target > root.val){
return find(root.right, target, prev);
}
return prev;
}
}
下面是论坛上的写法，思想一致，更取巧了一些。
public int closestValue(TreeNode root, double target) {
TreeNode node = (root.val>target)?root.left:root.right;
if (node == null) {
return root.val;
}
int value = closestValue(node, target);
return Math.abs(root.val-target) > Math.abs(value-target)?value:root.val;
}
这道题是在二叉树上做 range query.
二叉树上做 range query 普遍要依靠 getPrev() 和 getNext() 函数，或者利用 Parent 指针做 traversal.
但是 BST 不一样，如上题所说， inorder 是 BST 的灵魂。因此这道题可以分为三部分；
做出 inorder traversal list
只在主函数的起始 index 上出了一个小 bug，基本算是一次 AC.
时间复杂度 O(n) + O(log n) + O(k) = O(n)
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> inorder = inorder(root);
int index = binarySearch(inorder, target);
List<Integer> list = new ArrayList<Integer>();
int start = index - 1;
int end = index;
while(start >= 0 && end < inorder.size()){
int num = (Math.abs(inorder.get(start) - target) < Math.abs(inorder.get(end) - target))
? inorder.get(start--)
: inorder.get(end++);
list.add(num);
if(list.size() == k) return list;
}
while(start >= 0){
list.add(inorder.get(start--));
if(list.size() == k) return list;
}
while(end < inorder.size()){
list.add(inorder.get(end++));
if(list.size() == k) return list;
}
return list;
}
private List<Integer> inorder(TreeNode root){
List<Integer> list = new ArrayList<Integer>();
TreeNode cur = root;
while(cur != null){
if(cur.left == null){
list.add(cur.val);
cur = cur.right;
} else {
TreeNode prev = cur.left;
while(prev.right != null && prev.right != cur){
prev = prev.right;
}
if(prev.right == null){
prev.right = cur;
cur = cur.left;
} else {
prev.right = null;
list.add(cur.val);
cur = cur.right;
}
}
}
return list;
}
private int binarySearch(List<Integer> list, double target){
int start = 0;
int end = list.size() - 1;
while(start + 1 < end){
int mid = start + (end - start) / 2;
if(list.get(mid) == target){
return mid;
} else if(target < list.get(mid)){
end = mid;
} else {
start = mid;
}
}
if(target < list.get(start)) return start;
if(target > list.get(end)) return end;
return (Math.abs(list.get(start) - target) < Math.abs(list.get(end) - target)) ? start: end;
}
}
LeetCode 论坛上还有一些其他的写法，也很有意思。这个写法是 O(n log n) + O(k log n)，用自定义的 min heap.
public List<Integer> closestKValues(TreeNode root, final double t, int k) {
List<Integer>ret = new ArrayList<Integer>();
PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>(new Comparator<TreeNode>(){
public int compare(TreeNode n1, TreeNode n2) {
return Math.abs(n1.val - t) < Math.abs(n2.val - t) ? -1 : 1;
}
});
findClosest(root, queue);
while(k-- > 0) ret.add(queue.poll().val);
return ret;
}
public void findClosest(TreeNode root, PriorityQueue<TreeNode> queue) {
if(root == null) return;
findClosest(root.left, queue);
queue.add(root);
findClosest(root.right, queue);
}
Java 內建的 LinkedList 库是双向链表，implements Deque.
这个解法我很喜欢，类似于 sliding window maximum 一样，维护一个大小为 k 的 sliding window，在树上做 inorder traversal，每当 window size == k 但是新 node 值比 head 的值更接近于 target 的时候，就给替换掉。当后来发现新来的 node 不比 head 更接近于 target 的时候，就可以返回结果了，而且因为 LinkedList 继承了 List，连类型转换都不需要。
时间复杂度 O(n) ，还带 early termination，非常简洁高效的解法，比我写的那个速度快，而且简洁明了。
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new LinkedList<Integer>();
helper(root, target, k, res);
return res;
}
private void helper(TreeNode root, double target, int k, List<Integer> res) {
if (root == null) {
return;
}
helper(root.left,target,k,res);
if (res.size()< k) {
res.add(root.val);
} else {
if (Math.abs(res.get(0)-target) > Math.abs(root.val-target)) {
res.remove(0);
res.add(root.val);
} else {
return;
}
}
helper(root.right,target,k,res);
}