96. Unique Binary Search Trees

Leetcode

https://leetcode.com/problems/unique-binary-search-trees/

題目

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

解答

• 方法一

這一題其實跟前一題 95. 一模一樣，差別在前一題要求出整個樹狀結構，但這一題只需要求出數量就好，所以我們可以使用 95. 題中遞迴的解法，改成回傳數量就是這題要的答案

var numTrees = function (n) {
    const checkNumTrees = (start, end) => {
        let totalNums = 0;

        if (start > end) {
            return 1;
        }
        if (start === end) {
            return 1;
        }

        for (let i = start; i <= end; i++) {
            const leftTreeNums = checkNumTrees(start, i - 1);
            const rightTreeNums = checkNumTrees(i + 1, end);
            
            // 左右子樹的數量相配對後，再加進來
            totalNums += leftTreeNums * rightTreeNums;
        }

        return totalNums;
    }

    return checkNumTrees(1, n);
};

更進一步來看，由於這題只需要求 BST 的數量，因此 const leftTreeNums = checkNumTrees(start, i - 1); 這行實際上不用傳入 start 跟 end 的數值，只需要傳入節點的數量就可以，例如：start=1, end=3 => 總共有五種組合，換成 start=5, end=7 一樣也是五種組合

因此以上可以改寫為：

var numTrees = function (n) {
    const checkNumTrees = (n) => {
        let totalNums = 0;

        // 0 個或 1 個節點都回傳 1
        if (n === 0 || n === 1) {
            return 1;
        }

        for (let i = 1; i <= n; i++) {
            const leftTreeNums = checkNumTrees(i - 1);
            const rightTreeNums = checkNumTrees(n - i);

            totalNums += leftTreeNums * rightTreeNums;
        }

        return totalNums;
    }

    return checkNumTrees(n);
};

雖然這個解法的方向是對的，但實際跑時會發現當 n 太大時導致了 Time Limit Exceeded

所以我們需要能夠快取節點的數量，就像上面提到只要 checkNumTrees 函式傳入的 n 是一樣的，回傳的 totalNums 也會是一樣的數值

var numTrees = function (n) {
    // 利用 map 快取 n 與樹狀結構總數的關係
    const map = {};

    const checkNumTrees = (n) => {
        if (n in map) {
            return map[n];
        }

        let totalNums = 0;

        if (n === 0 || n === 1) {
            return 1;
        }

        for (let i = 1; i <= n; i++) {
            const leftTreeNums = checkNumTrees(i - 1);
            const rightTreeNums = checkNumTrees(n - i);

            totalNums += leftTreeNums * rightTreeNums;
        }

        map[n] = totalNums;

        return totalNums;
    }

    return checkNumTrees(n);
};

Runtime: 47 ms Beats 75.77% of users with JavaScript

Memory: 48.96 MB Beats 20.14% of users with JavaScript