[leetcode]95. Unique Binary Search Trees II

左手的ㄟ右手 2022-07-21 02:22 158阅读 0赞

题目链接：[95. Unique Binary Search Trees II][]

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

For example,  
Given n = 3, your program should return all 5 unique BST’s shown below.  
![BST example][]

读完这道题目，显然这道题的解法一定含有递归的元素在内。因为我们如果想要知道n个结点的所有BST排列方法，则一定要知道(n-1)个结点情况下的所有BST排列方法，则进一步需要(n-2)个结点情况下的所有BST排列方法。但同时我们也注意到，如果用简单的递归思路去做的话，会不断重复求解子问题。这就影响了算法的效率。那么很自然就想到用动态规划的思路去解决这个问题了。（动态规划的思想是什么？记忆（cache），时间换空间，不求重复解，由交叠子问题从较小问题逐步决策从而构造较大子问题的解，进而得出整个问题的解）。其满足动态规划的两大要素：交叠子问题(overlapping subproblems)（要想求n需要求n-1, n-2, … 而要想求n-1需要先求n-2, n-3, …）和最优子结构(optimal substructure)。  
那么接下来就是要思考具体如何安排交叠子问题和最优子结构了。

我们知道树的结构使其天然地适合使用递归的算法。  
同时，我们如果想要知道n个结点的全部BST，则我们需要考虑这n个结点每一个作为根结点时的情况。例如我们使用第i个结点作为根结点，那么此时就产生了两个子问题：左子树怎么安排？右子树怎么安排？根据BST的性质，左子树也就是第1到i-1个结点构成的所有BST，右子树也就是从第i+1到第n个结点构成的所有BST。到这一步，交叠子问题和最优子结构就很明确了。  
根据以上分析，我们得出以下递归算法：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            /*
            If we want to know all different BST of n nodes, we may need to consider the condition in which each of the node can be the root. And in each conditon, we need to consider 2 subproblems, which is the left subtree and right subtree. If we use, say, the ith node to be the root, than we have to consider how left subtrees contain nodes 0 to i-1 look like and how right subtrees contain nodes i+1 through n look like. Then we have subproblem of subproblem. Apparently this is a dynamic programming problem. We could use cache to reduce the run time, which, in this case, is to cache the different subtree structures of nodes. 
            */
            if (n == 0){
                List<TreeNode> result = new ArrayList<TreeNode>();
                return result;
            }
            int[] numoftree = numOfBST(n);
    
            TreeNode[] resultarr = generateSubTrees(1, n, numoftree);
    
            List<TreeNode> result= new ArrayList<TreeNode>();
    
            for (int i = 0; i < resultarr.length; i++) {
                result.add(resultarr[i]);
            }
            return result;
        }
    
        private TreeNode[] generateSubTrees(int start, int end, int[] dp) {
            TreeNode[] resultarr = new TreeNode[dp[end - start + 1]];
            int currpos = 0;
            if (start > end) {
                resultarr[0] = null;
                return resultarr;
            }
            for (int i = start; i <= end; i++) {
                TreeNode[] nodeL = generateSubTrees(start, i - 1, dp);
                TreeNode[] nodeR = generateSubTrees(i + 1, end, dp);
                for (TreeNode nodel : nodeL) {
                    for (TreeNode noder : nodeR) {
                        TreeNode root = new TreeNode(i);
                        root.left = nodel;
                        root.right = noder;
                        resultarr[currpos] = root;
                        currpos++;
                    }
                }
            }
            return resultarr;
        }
    
        private int[] numOfBST(int n) {
            /*
            use dynamic programming to calculate the number of different BST
            */
            int[] num = new int[n+1];
            num[0] = 1;
            if (n == 0){
                return num;
            }
            num[1] = 1;
            for (int i = 2; i <= n; i++){
                for (int j = 1; j <= i; j++){
                    num[i] += num[j - 1] * num[i - j];
                }
            }
            return num;
        }
    }

以上方法是没有使用记忆的。根据之前的分析，在这个算法中使用记忆需要构造一个三维数组。其中前两位分别对应BST的开始结点和结束结点的信息，第三位保存这些结点构成的BST。如下所示：

List<List<List<TreeNode>>> BSTcache = new ArrayList<List<List<TreeNode>>>;

我们可以使用如下方法来进行初始化操作：

for (int i = 0; i < n; i++){
        List<List<TreeNode>> yrow = new ArrayList<List<TreeNode>>(n);
        BSTcache.add(yrow);
        for(int j = 0; j < n; j++){
            List<TreeNode> zrow = new ArrayList<TreeNode>();
            BSTcache.get(i).add(zrow);
        }
    }

这样我们就创造了一个前两维为n∗n而第三维大小不定的三维动态数组。我们用`BSTcache.get(i).get(j)`即可取出从第i个结点开始到第j个结点结束的所有BST构成的ArrayList。  
然而这样做太过麻烦。

根据cracking the coding interview中的优化理念，我们首先考虑优化BUD(Bottleneck, Unnecessary work, Duplicated work)。显然其中的Duplicated work已经在动态规划的缓存这一步被解决了。而Bottleneck又不是很明显，那么只能寻找Unnecessary work了。  
根据BST的对称性（既：i+1到n结点构成的BST和从1到n-i结点构成的DST结构完全相同，只有结点数值的区别。）那么我们可以用这一点减少数组的一个维度，只用二位数组来缓存。既数组的第一个维度i代表从第1个结点到第i个结点，第二个维度存储从第1到第i个结点的所有BST。通过这种方法，我们解决了Unnecessary work。  
之所以代码中只对右子树使用clone方法，是因为只有右子树中的结点的值需要被改变（原因如上）。而offset参数即是需要改变的大小。  
如以下代码所示：

public class Solution{
        public List<TreeNode> generateTrees(int n) {
            List<TreeNode>[] result = new List[n+1];
            result[0] = new ArrayList<TreeNode>();
            result[0].add(null);
            if (n == 0){
                //OJ requires to return [], so we cannot just return result[0] which is [[]].
                return new ArrayList<TreeNode>();
            }
    
            for (int len = 1; len <= n; len++){
                //result[i] stores the root of different BSTs for node number equals i
                //since we don't know how many different BSTs are there, we use ArrayList to store roots
                result[len] = new ArrayList<TreeNode>();
                for (int j = 0; j < len; j++){
                    //use result j as left subtree and j+1 as the root
                    for (TreeNode nodeL : result[j]){
                        for (TreeNode nodeR : result[len - 1 - j]){
                            //use result j+1(not included) through len as the right subtree, however, the tree structure of result j+1 through len is similar to 0 through len-1-j while only the node values have a difference of j+1
                            TreeNode root = new TreeNode(j+1);
                            root.left = nodeL;
                            //since we are using result[len-1-j] as the right subtree, we only have to change the values of each node with the clone method.
                            root.right = clone(nodeR, j + 1);
                            result[len].add(root);
                        }
                    }
                }
            }
            return result[n];
        }
        private static TreeNode clone(TreeNode node, int offset){
            //change the value of each node to val+offset
            if (node == null){
                return null;
            }
            TreeNode root = new TreeNode(node.val + offset);
            root.left = clone(node.left, offset);
            root.right = clone(node.right, offset);
            return root;
        }
    }

[95. Unique Binary Search Trees II]: https://leetcode.com/problems/unique-binary-search-trees-ii/
[BST example]: /images/20220720/2c67238ec70c49b781c5835f15ad7aa1.png