LeetCode: 95. Unique Binary Search Trees II

题目描述

Given an integer 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, 生成 1 到 n 构成的 BST(二分查找树) 的所有情况。

解题思路 —— 递归求解

分别以待求区间内的某个元素作为根节点，小于它的值的元素作为其左子树的元素，大于它的值的元素作为右子树，递归的生成所有可能的情况。

另外，由于计算的始终是 1…n 的 BST, 因此可以记录下已经计算的结果，以节省时间。

AC 代码

• 朴素算法(19 ms, beats 26.67 %)

/** * 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 {
private:
    // 生成 [beg, end) 区间的 BST 子树
    vector<TreeNode*> generateTreesRef(int beg, int end)
    {
        if(beg >= end) return { nullptr };

        vector<TreeNode*> trees;

        // 分别以 [beg, end) 区间的元素作为根节点
        for(int rootVal = beg; rootVal < end; ++rootVal)
        {
            vector<TreeNode*> leftChildTrees = generateTreesRef(beg, rootVal);
            vector<TreeNode*> rightChildTrees = generateTreesRef(rootVal+1, end);

            // 这里共用相同的子树, 如果不共用，则可以每次使用的时候复制一遍子树。
            for(TreeNode* leftChild : leftChildTrees)
            {
                for(TreeNode* rightChild : rightChildTrees)
                {
                    TreeNode* root = new TreeNode(rootVal);
                    root->left = leftChild;
                    root->right = rightChild;
                    trees.push_back(root);
                }
            }
        }

        return trees;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0) return {};
        return generateTreesRef(1, n+1);
    }
};

• 记忆搜索(16 ms, beats 97.18 %)

/** * 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 {
private:
    // 生成 [beg, end) 区间的 BST 子树
    vector<TreeNode*> generateTreesRef(int beg, int end, map<pair<int,int>, vector<TreeNode*>>& cache)
    {
        if(beg >= end) return { nullptr };
        auto begEnd = make_pair(beg, end);
        auto iter = cache.find(begEnd);
        if(iter != cache.end()) return iter->second;

        vector<TreeNode*> trees;

        // 分别以 [beg, end) 区间的元素作为根节点
        for(int rootVal = beg; rootVal < end; ++rootVal)
        {
            vector<TreeNode*> leftChildTrees = generateTreesRef(beg, rootVal, cache);
            vector<TreeNode*> rightChildTrees = generateTreesRef(rootVal+1, end, cache);

            // 这里共用相同的子树, 如果不共用，则可以每次使用的时候复制一遍子树。
            for(TreeNode* leftChild : leftChildTrees)
            {
                for(TreeNode* rightChild : rightChildTrees)
                {
                    TreeNode* root = new TreeNode(rootVal);
                    root->left = leftChild;
                    root->right = rightChild;
                    trees.push_back(root);
                }
            }
        }
        cache[begEnd] = trees;

        return trees;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0) return {};
        // 记录已经计算过的结果
        static map<pair<int,int>, vector<TreeNode*>> cache;
        return generateTreesRef(1, n+1, cache);
    }
};