[LeetCode] 95. Unique Binary Search Trees II 獨(dú)一無(wú)二的二叉搜索樹(shù)之二

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

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

這道題是之前的 Unique Binary Search Trees 的延伸，之前那個(gè)只要求算出所有不同的二叉搜索樹(shù)的個(gè)數(shù)，這道題讓把那些二叉樹(shù)都建立出來(lái)。這種建樹(shù)問(wèn)題一般來(lái)說(shuō)都是用遞歸來(lái)解，這道題也不例外，劃分左右子樹(shù)，遞歸構(gòu)造。這個(gè)其實(shí)是用到了大名鼎鼎的分治法 Divide and Conquer，類似的題目還有之前的那道 Different Ways to Add Parentheses 用的方法一樣，用遞歸來(lái)解，劃分左右兩個(gè)子數(shù)組，遞歸構(gòu)造。剛開(kāi)始時(shí)，將區(qū)間 [1, n] 當(dāng)作一個(gè)整體，然后需要將其中的每個(gè)數(shù)字都當(dāng)作根結(jié)點(diǎn)，其劃分開(kāi)了左右兩個(gè)子區(qū)間，然后分別調(diào)用遞歸函數(shù)，會(huì)得到兩個(gè)結(jié)點(diǎn)數(shù)組，接下來(lái)要做的就是從這兩個(gè)數(shù)組中每次各取一個(gè)結(jié)點(diǎn)，當(dāng)作當(dāng)前根結(jié)點(diǎn)的左右子結(jié)點(diǎn)，然后將根結(jié)點(diǎn)加入結(jié)果 res 數(shù)組中即可，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return helper(1, n);
    }
    vector<TreeNode*> helper(int start, int end) {
        if (start > end) return {nullptr};
        vector<TreeNode*> res;
        for (int i = start; i <= end; ++i) {
            auto left = helper(start, i - 1), right = helper(i + 1, end);
            for (auto a : left) {
                for (auto b : right) {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    res.push_back(node);
                }
            }
        }
        return res;
    }
};

我們可以使用記憶數(shù)組來(lái)優(yōu)化，保存計(jì)算過(guò)的中間結(jié)果，從而避免重復(fù)計(jì)算。注意這道題的標(biāo)簽有一個(gè)是動(dòng)態(tài)規(guī)劃 Dynamic Programming，其實(shí)帶記憶數(shù)組的遞歸形式就是 DP 的一種，memo[i][j] 表示在區(qū)間 [i, j] 范圍內(nèi)可以生成的所有 BST 的根結(jié)點(diǎn)，所以 memo 必須是一個(gè)三維數(shù)組，這樣在遞歸函數(shù)中，就可以去 memo 中查找當(dāng)前的區(qū)間是否已經(jīng)計(jì)算過(guò)了，是的話，直接返回 memo 中的數(shù)組，否則就按之前的方法去計(jì)算，最后計(jì)算好了之后要更新 memo 數(shù)組，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        vector<vector<vector<TreeNode*>>> memo(n, vector<vector<TreeNode*>>(n));
        return helper(1, n, memo);
    }
    vector<TreeNode*> helper(int start, int end, vector<vector<vector<TreeNode*>>>& memo) {
        if (start > end) return {nullptr};
        if (!memo[start - 1][end - 1].empty()) return memo[start - 1][end - 1];
        vector<TreeNode*> res;
        for (int i = start; i <= end; ++i) {
            auto left = helper(start, i - 1, memo), right = helper(i + 1, end, memo);
            for (auto a : left) {
                for (auto b : right) {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    res.push_back(node);
                }
            }
        }
        return memo[start - 1][end - 1] = res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(95.獨(dú)一無(wú)二的二叉搜索樹(shù)之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)獨(dú)一無(wú)二的二叉搜索樹(shù)之二內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論