子树组合，BST query

Java 带泛型的 Collections 确实是可以放 null 的， 比如 Queue, List...

Unique Binary Search Trees

这题考察的是 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];
    }
}

Unique Binary Search Trees II

顺着上题的思路，这题也很好做。让我比较惊讶的是改好了拼写之后居然一次提交直接 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;
    }
}

Closest Binary Search Tree Value

比较简单的问题，唯一需要考虑的是状态的不连续性；最接近的点可能是 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;
}

Closest Binary Search Tree Value II

这道题是在二叉树上做 range query.

二叉树上做 range query 普遍要依靠 getPrev() 和 getNext() 函数，或者利用 Parent 指针做 traversal.

但是 BST 不一样，如上题所说， inorder 是 BST 的灵魂。因此这道题可以分为三部分；

• 做出 inorder traversal list

• 找 target 对应的 index

• 从 index 两边扫，寻找 k 个元素

只在主函数的起始 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);
}

Diameter of a Binary Tree