欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

C++二叉搜索樹實(shí)例分析

本篇內(nèi)容介紹了“C++二叉搜索樹實(shí)例分析”的有關(guān)知識,在實(shí)際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)張家口免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都,凝聚了一批互聯(lián)網(wǎng)行業(yè)人才,有力地推動了近1000家企業(yè)的穩(wěn)健成長,幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

獨(dú)一無二的二叉搜索樹

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

解法一:

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ù)組來優(yōu)化,保存計(jì)算過的中間結(jié)果,從而避免重復(fù)計(jì)算。注意這道題的標(biāo)簽有一個(gè)是動態(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ì)算過了,是的話,直接返回 memo 中的數(shù)組,否則就按之前的方法去計(jì)算,最后計(jì)算好了之后要更新 memo 數(shù)組,參見代碼如下:

解法二:

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;
    }
};

“C++二叉搜索樹實(shí)例分析”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!

文章題目:C++二叉搜索樹實(shí)例分析
分享鏈接:http://www.aaarwkj.com/article46/ipdoeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供用戶體驗(yàn)、搜索引擎優(yōu)化、微信公眾號、域名注冊、網(wǎng)站改版、網(wǎng)站制作

廣告

聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)

成都做網(wǎng)站
国产黄色大片在线关看| 麻豆视传媒短视频免费看| 国产熟乱老女人露脸视频| 妞妞婷婷基地五月天| 免费无遮挡18禁视频| 激情欧美精品桃桃激情| 亚洲综合成人av在线| 国产一级一片内射在线| 日韩女同性一区二区三区| 国产美女极度色诱视频| 精品国产美女主播在线| 亚洲精品aa片在线观看国产| 欧美激情性国产精品潮| 91精品大片免费在线观看| 五月激情开心久久婷婷| 国产美女口爆吞精久久| 国产精品一品二品国精品| 国产一区二区三区精品女同| av在线手机中文字幕| 欧美日韩电影一区二区三区在线观看 | 青青草免费公开视频久久| 国产成人精品亚洲av无人区| 亚洲精品黄色在线观看| 熟女人妻丰满视频中文字幕| 日韩女优中文字幕在线播放| 中文字幕欧美人妻在线| 日韩一区二区三区av观看| 欧美口爆吞精在线观看| 91好色视频在线观看| 日韩欧美一区二区三区在线| 国产色综合一区二区| 亚洲最大成人av在线| 亚欧熟女乱色一二三区日韩| 午夜福利大片在线观看视频| 中文字幕在线看精品乱码| 国产在线精品91系列| 欧美日韩亚洲精品瑜伽裤| 国产一级二级三级在线电影| 青青草视频在线针对华人| 91精品蜜臀国产综合久久久久久 | 亚洲日本在线观看午夜视频|