• 关键字:二叉搜索树、动态规划、递推
  • 难度:中等
  • 前置知识:二叉搜索树
  • 题目大意:计算出所有由1~N构成的二叉搜索树。

题目描述

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example, Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解法

这道题目要求给出所有的方案,所以在实际的编写过程中,可以采用搜索来进行计算,因为对具体方案的处理会将动态规划的复杂度也拉到和搜索一个级别上,但是做人没有梦想,和咸鱼有什么区别呢?所以我们不妨来看看,如何使用动态规划来解决这道题目。

我们不妨将问题关于规模n进行抽象,即S(K)表示1~K构成的所有二叉搜索树组成的集合,而我们的答案就是S(n)

那么如何求解S(K)呢?

我们不妨枚举根节点root的取值j,不难发现,root的左子树必然是一个1~(j-1)的二叉搜索树,root的右子树必然是一个j+1~K的二叉搜索树。

特别的,如果我们把root的右子树中的所有取值都减去j,那么root的右子树必然是一个1~(K-j)的二叉搜索树。

也就是说,如果我们已经计算出了S(j-1)S(K-j),我们就可以通过枚举S(j-1)中的一个元素和S(K-j)中的一个元素,来拼接成所有的S(K),即可以通过将S(K)转化为更小规模的问题来完成计算。

所以我们可以按照递推的方式,从K=1开始依次对S(K)进行计算,并且在最后计算S(n)

参考代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 复制一颗子树,并且对其中所有元素都加上bias
    static TreeNode* copy(TreeNode *root, int bias) {
        if (root == NULL) return NULL;
        TreeNode *p = new TreeNode(root -> val + bias);
        p -> left = copy(root -> left, bias);
        p -> right = copy(root -> right, bias);
    }
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<TreeNode *>> ans;
        // S[0]
        ans.push_back(vector<TreeNode *>());
        ans[0].push_back(NULL);
        // 递推的计算S[1]~S[n]
        for (int i = 1; i <= n; i++) {
            ans.push_back(vector<TreeNode *>());
            // 枚举根节点的取值
            for (int j = 1; j <= i; j++) {
                // 枚举左右子树的方案
                for (int l = 0; l < ans[j - 1].size(); l++)
                    for (int r = 0; r < ans[i - j].size(); r ++) {
                        // 拼接为一个新的方案
                        TreeNode *root = new TreeNode(j);
                        root -> left = copy(ans[j - 1][l], 0);
                        root -> right = copy(ans[i - j][r], j);
                        ans[i].push_back(root);
                    }
            }
        }
        // 返回S[n]
        return ans[n];
    }
};

登录发表评论 注册

反馈意见