# 子树组合，BST query

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

## [Unique Binary Search Trees](https://leetcode.com/problems/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 的代码，有点粗糙。

```java
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](https://leetcode.com/problems/unique-binary-search-trees-ii/)

顺着上题的思路，这题也很好做。让我比较惊讶的是改好了拼写之后居然一次提交直接 AC....

```java
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 用就可以让代码变得非常简洁。

```java
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](https://leetcode.com/problems/closest-binary-search-tree-value/)

比较简单的问题，唯一需要考虑的是状态的不连续性；最接近的点可能是 BST 一直往下走的 node，也可能是前面某个 node.

用区间的思想去理解的话，每个 node 都有自己的 valid 区间，区间与区间是重合的。对于给定 target，我们先要找到 target 是什么，然后决定 target 到底靠近重合区间的左边还是右边。

```java
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;
    }
}
```

下面是论坛上的写法，思想一致，更取巧了一些。

```java
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](https://leetcode.com/problems/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)

```java
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.

```java
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，非常简洁高效的解法，比我写的那个速度快，而且简洁明了。

```java
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](http://www.geeksforgeeks.org/diameter-of-a-binary-tree/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/68-_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.