力扣：96. 不同的二叉搜尋樹

 初拿到這題時，很自然的就想到用遞歸來做。

然後就有了下面的解法，最終執行沒問題，隻是逾時了，明天優化一下。

public class Solution {

    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            // 把 i 當成父節點
            int left = compute(i, 1, i - 1, 0);
            int right = compute(i, i + 1, n, 1);
            res += left != 0 && right != 0 ? left * right : (left != 0 ? left : right);
        }
        return res;
    }

    // 大問題拆解成小問題來做就很棒
    private int compute(int father, int begin, int end, int turn) {
        if (begin > end) {
            return 0;
        }
        // 0 左子樹 1 右子樹
        if (begin == end) {
            return 1;
        }
        int lenMin = 0;
        int lenMax = 0;
        if (turn == 0) {
            // 左子樹
            lenMax = father - 1;
        } else {
            // 右子樹
            lenMin = father + 1;
        }
        int left = 0, right = 0;
        int res = 0;
        for (int i = begin; i <= end; i++) {
            left = 0;
            right = 0;
            // 這一步是選擇子節點來的
            if (turn == 0) {
                // 左子樹
                left += compute(i, begin, i - 1, 0);
                // 右子樹
                right += compute(i, i + 1, lenMax, 1);
            } else {
                // 左子樹
                left += compute(i, lenMin, i - 1, 0);
                // 右子樹
                right += compute(i, i + 1, end, 1);
            }
            res += left != 0 && right != 0 ? left * right : (left != 0 ? left : right);
        }
        return res;
    }
}
           

看了一下時間，現在是淩晨12點18分，已經到了明天了，是以我試着優化了一下，主要就是存儲遞歸過程中的一些數值，減少了重複計算。

這次沒有逾時

public class Solution {

    private static Map<String, Integer> map = new HashMap<>();

    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            // 把 i 當成父節點
            int left = compute(i, 1, i - 1, 0);
            int right = compute(i, i + 1, n, 1);
            res += left != 0 && right != 0 ? left * right : (left != 0 ? left : right);
        }
        return res;
    }

    // 大問題拆解成小問題來做就很棒
    private int compute(int father, int begin, int end, int turn) {
        if (begin > end) {
            return 0;
        }
        // 0 左子樹 1 右子樹
        if (begin == end) {
            return 1;
        }
        int lenMin = 0;
        int lenMax = 0;
        if (turn == 0) {
            // 左子樹
            lenMax = father - 1;
        } else {
            // 右子樹
            lenMin = father + 1;
        }
        int left = 0, right = 0;
        int res = 0;
        for (int i = begin; i <= end; i++) {
            left = 0;
            right = 0;
            // 這一步是選擇子節點來的
            if (turn == 0) {
                // 左子樹
                int tempLeft = map.get("left:" + (i - 1 - begin)) == null ? compute(i, begin, i - 1, 0) : map.get("left:" + (i - 1 - begin));
                left += tempLeft;
                map.put("left:" + (i - 1 - begin), tempLeft);
                // 右子樹
                int tempRight = map.get("right:" + (lenMax - i - 1)) == null ? compute(i, i + 1, lenMax, 1) : map.get("right:" + (lenMax - i - 1));
                right += tempRight;
                map.put("right:" + (lenMax - i - 1), tempRight);
            } else {
                // 左子樹
                int tempLeft = map.get("left:" + (i - 1 - lenMin)) == null ? compute(i, lenMin, i - 1, 0) : map.get("left:" + (i - 1 - lenMin));
                left += tempLeft;
                map.put("left:" + (i - 1 - lenMin), tempLeft);
                // 右子樹
                int tempRight = map.get("right:" + (end - i - 1)) == null ? compute(i, i + 1, end, 1) : map.get("right:" + (end - i - 1));
                right += tempRight;
                map.put("right:" + (end - i - 1), tempRight);
            }
            res += left != 0 && right != 0 ? left * right : (left != 0 ? left : right);
        }
        return res;
    }

}