LeetCode 96 Unique Binary Search Trees

标签: 二叉搜索树 LeetCode 发布于:2022-02-07 13:39:12 编辑于:2022-02-07 14:25:58 浏览量:962

概述

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

动态规划法

拿到题目,第一反应可以根据第 n-1 的个数推断出 n 的个数。

仔细想了想,貌似挺麻烦的。

其实可以通过遍历一遍轮流作为根节点来解决问题。

class Solution {
public:
    vector<int> dp;
    int numTrees(int n) {
        vector<int> dp(n+1, -1);
        dp[0] = 1;
        dp[1] = 1;
        this->dp = dp;
        return helper(n);
    }
    
    int helper(int n) {
        if (dp[n] != -1) return dp[n];
        int count = 0;
        for (int i = 0; i < n; i ++) {
            int ln = i - 0;
            int rn = n - i - 1;
            count += helper(ln) * helper(rn);
        }
        dp[n] = count;
        return count;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/