LeetCode: Unique Binary Search Trees I && II

思路分析

第一题是一个二维动态规划问题，说白了还是有点类似找规律。首先可以发现，不同BST可以依据它的根节点来分类。考虑到BST的性质，对于以元素i为根节点的BST，它的左子树元素一定是[1,i-1]，右子树元素一定是[i+1,n]。这样，我们枚举根节点位置，计算对应于每个根节点的BST个数，加在一起就是总的BST个数。
考虑边界条件：显然有dp[0]=dp[1]=1，含义是空树和只有一个节点的树。于是就有状态转移方程：\(dp_{n}=\Sigma^{n-1}_{k=0}{dp_{k}*dp_{n-k-1}}\)。它的含义是，对于整数[1,n]组成的BST，其不同构造方法的个数，等于枚举其中的每一个元素作为BST根节点，左右子树各自不同构造数乘积的总和。总而言之，还是要利用到树的递归性质。

第二题就稍微繁琐一些了，要求你再构造出所有可能的不同BST。核心思路还是一样的，只不过需要手动操作树的深度复制以及合并。另外注意复制一个子树的时候，不单单是简单的递归复制，而是还需要考虑到对于右子树，需要手动为其加上根节点的值，手动模拟一下就能看出来这是为什么了。总而言之，代码要实现得简洁漂亮。

代码

第一问

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

const int MAX = 1000;
int dp[MAX];

class Solution {
public:
    int numTrees(int n) {
        CLR(dp, 0);
        dp[0] = dp[1] = 1;
        dp[2] = 2;
        REP(i, 3, n + 1)
            rep(k, i) dp[i] += dp[k] * dp[i - k - 1];
        return dp[n];
    }
};

第二问

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    static const int MAX = 100;
    vector<TreeNode *> dp[MAX];
    vector<TreeNode *> generateTrees(int n) {
        rep(i, n + 1) dp[i].clear();
        dp[0].PB(NULL);
        dp[1].PB(new TreeNode(1));
        REP(i, 2, n + 1) {
            rep(k, i) {
                rep(l, dp[k].size())
                rep(r, dp[i - k - 1].size()) {
                    TreeNode *root = new TreeNode(k + 1);
                    root->left = deepClone(dp[k][l], 0);
                    root->right = deepClone(dp[i - k - 1][r], k + 1);
                    dp[i].PB(root);
                }
            }
        }
        return dp[n];
    }
    TreeNode *deepClone( TreeNode *root, int val )
    {
        if ( root == NULL ) return root;
        TreeNode *res = new TreeNode(root->val + val);
        res->left = deepClone(root->left, val);
        res->right = deepClone(root->right, val);
        return res;
    }
};