Leetcode 题目解析之 Unique Binary Search Trees

原创

ruochen

发布于 2022-02-28 13:09:28

1.3K00

代码可运行

文章被收录于专栏：若尘的技术专栏若尘的技术专栏

运行总次数：0

代码可运行

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

For example,

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

以n为根结点的二叉树个数=左子树个数*右子树个数

用数组recordn+1记录以0~n的情况，自底向上，否则会超时

    public int numTrees(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        // record[0]没有用，所以长度是n+1
        // 使用数组，从下向上保存结果，能够节省时间，否则会超时
        int[] record = new int[n + 1];
        record[0] = 1;
        record[1] = 1; // 1个元素时，情况为1
        record[2] = 2; // 2个元素时，情况为2
        for (int i = 3; i <= n; i++) {
            int tmp = 0;
            for (int k = 0; k < i; k++) {
                // 以n为根结点的二叉树个数=左结点的二叉树个数*右结点的二叉树个数
                // 题目所求要包括所有情况，分别以1~n为根结点
                tmp += (record[k] * record[i - k - 1]);
            }
            // 记录1~i时，BST的个数
            record[i] = tmp;
        }
        return record[n];
    }