ARTS打卡：第五周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

这周将 Recursion I 剩余部分完成了，记录如下：

96. Unique Binary Search Trees(Medium)

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
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

@DevDocsleetcode.com/problems/unique-binary-search-trees

题目意思：给定n值，求出有多少结构上唯一的存储值1 … n的BST（二叉搜索树）？

首先我们要了解二叉搜索树（BST binary search trees）是什么?

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

任意节点的左、右子树也分别为二叉查找树；

没有键值相等的节点。

@DevDocszh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9

思路来源：
DP Solution in 6 lines with explanation. F(i, n) = G(i-1) * G(n-i)-G(i-1)-*-G(n-i))

这个帖子说的很详细，建议小伙伴们都看看。

代码如下：


class Solution {
    public int numTrees(int n) {
        // 为了方便理解，申请长度为 n+1 的数组，便于最后直接返回 g[n]
        int[] g = new int[n + 1];
        // base case
        g[0] = g[1] = 1;
        // 从g(2)出发
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // g(n) = f(1, n) + ... + f(n, n)
                // f(i, n) = g(i -1) * g(n - i)
                // g(n) = g(0) * g(n - 1) + ... + g(n - 1) * g(0)
                g[i] += g[j -1] * g[i - j];
            }
        }
        return g[n];
    }
}

95. Unique Binary Search Trees II(Medium)

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST’s shown below:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

@DevDocsleetcode.com/problems/unique-binary-search-trees

题目意思：给定整数n，生成存储值1 … n的所有结构上唯一的BST（二叉搜索树）。

思路：
其实跟上面那道题的思路很相像，这里大致说下：

我们从 Example 可得出如果 n 是输入值的话，那么根节点可能就是 1-n 中任何一个。
我们可以先假设 G(n) = G(start, end) 能获取生成存储值1 … n的所有结构上唯一的BST，start是 1-n 范围内的起点，end 是终点，即 n。
因为是BST，所以当i为根节点时，左子树的所有结果集可以假设为 G(start, i - 1)，，右子树的所有结果集可以假设为 G(i+1, n)。
确认 base case，能确认最底部的根节点，然后关联有可能的左子树和右子树，最后返回一个包含了所有的情况的集合，当 start > end 的时候，返回一个空集合，表示没有左/右子树。
确认边界条件，当 n == 0，直接返回空集合。

代码如下：

public List<TreeNode> generateTrees(int n) {
    // 边界条件
    if (n == 0) {
        return new ArrayList<>();
    }
    return genTrees(1, n);
}
private List<TreeNode> genTrees(int start, int end) {
    List<TreeNode> treeNodes = new ArrayList<>();
    //  base case
    if (start > end) {
        treeNodes.add(null);
        return treeNodes;
    }
    for (int i = start; i <= end; i++) {
        List<TreeNode> leftTreeNodes, rightTreeNodes;
        // 获取左子树的所有可能-递归公式
        leftTreeNodes = genTrees(start, i - 1);
        // 获取右子树的所有可能-递归公式
        rightTreeNodes = genTrees(i + 1, end);
        // base case
        for (TreeNode leftTreeNode :
                leftTreeNodes) {
            for (TreeNode rightTreeNode :
                    rightTreeNodes) {
                TreeNode root = new TreeNode(i);
                root.left = leftTreeNode;
                root.right = rightTreeNode;
                treeNodes.add(root);
            }
        }
    }
    return treeNodes;
}