LeetCode日记–95.96. Unique Binary Search Trees (II)

发布于 2020-10-02  109 次阅读


碎碎念:国庆假期,先猛学两天,再去玩两天,回来继续学。无法保研的彩笔流泪了。

这两题差不多,都是得到n个二叉搜索树(一个得到个数,一个是全部列出),故写在一起。

96题目如下:

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

Constraints:

1 <= n <= 19

95题目:

同样的输入,只不过返回值是一个存着所有可能的二叉搜索树的根节点的List。

思路:

思路一:普通递归

根据二叉搜索树的定义,可以很容易地把问题分解成一个一个的小问题。即每次遍历时,我们把比当前节点小的节点们放在左子树,比当前节点大的放在右子树。这时再遍历左右子树。选取左边集合中的某个节点作为左子树的根节点。左子树中小的,同理作为左子树的左子树,如此循环往复递归下去。

作为递归有一个重要的条件,那就是结束循环的条件。在本题中,因为需要得到所有可能的二叉搜索树的组合,因此结束递归的条件就是遍历完当前节点的所有左右子树。

95题递归代码如下(96题只需要在这个代码的基础上把返回的节点List变成计数并返回就可以了):

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = generateTrees(start, i - 1);

            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            // 从左子树集合中选出一棵左子树,从右子树集合中选出一棵右子树,拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路二:动态规划(Dynamic Programming)

对于第96题,我们可以知道DP[0](空树)、DP[1]都等于1,DP[2]=2(分别作为根)。

到目前为止好像都没有什么规律,这样不利于我们找到通项公式,那么我们再来看看DP[3]。我们发现有三种情况。首先,若3为根节点,则他比前面的节点都大,则前面的1,2都为他的右子树,那么这时右子树的可能性就有DP[2]个,左子树就是DP[0]个。所以3为根节点的情况就有DP[0]*DP[2]种可能性。同理得到2为根节点时为DP[1]*DP[1],1为根节点时为DP[0]*DP[2]。我们可以观察到,对于节点i,有DP[i]=DP[i-1-j]DP[i]的累求和(i从0到n-1),这就相当于把不同的节点当做根节点,就会有不同的数字成为左右子树的备选节点,然后对应的大小已经在之前计算过了。得到了通项公式我们就可以写DP的代码了。

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                G[i] += G[j ] * G[i - j-1];
            }
        }
        return G[n];
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这样的空间复杂度仍然是O(n),官方题解中推导出了卡塔兰数直接使用数学公式可以把空间复杂度降到O(1)。

不过第95题的动态规划解法我确实还没看懂,等看懂了再回来更新。


你好哇!欢迎来到雷公马碎碎念的地方:)