欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

python二叉樹(shù)問(wèn)題的示例分析

這篇文章給大家介紹python二叉樹(shù)問(wèn)題的示例分析，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

創(chuàng)新互聯(lián)公司10多年企業(yè)網(wǎng)站制作服務(wù);為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁(yè)設(shè)計(jì)及高端網(wǎng)站定制服務(wù),企業(yè)網(wǎng)站制作及推廣,對(duì)發(fā)電機(jī)維修等多個(gè)方面擁有多年的營(yíng)銷推廣經(jīng)驗(yàn)的網(wǎng)站建設(shè)公司。

題目鏈接

LeetCode 199. 二叉樹(shù)的右視圖[1]

 

題目描述

給定一棵二叉樹(shù)，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值。

示例1

輸入：[1,2,3,null,5,null,4]輸出:[1,3,4]解釋：   1            <--- /   \2     3         <--- \     \  5     4       <---
 

題解

 

dfs

dfs 的思路就是直接遞歸求解左右子樹(shù)各自能看到的右視圖是什么，然后判斷兩個(gè)視圖長(zhǎng)度。

如果右子樹(shù)右視圖長(zhǎng)度大于等于左子樹(shù)右視圖長(zhǎng)度，那左子樹(shù)完全被擋住。不用管左子樹(shù)了，直接返回根結(jié)點(diǎn)加上右子樹(shù)右視圖就行了。

否則的話，左子樹(shù)中超出右子樹(shù)深度的部分不會(huì)被擋住，也會(huì)被看到，所以得拼接在右子樹(shù)右視圖后面。

 

bfs

bfs 的思路就是層次遍歷了。對(duì)二叉樹(shù)的每一層，只取最后一個(gè)結(jié)點(diǎn)就行了。

bfs 的話就得用一個(gè)隊(duì)列來(lái)維護(hù)結(jié)點(diǎn)值了，那么怎么知道哪些結(jié)點(diǎn)是同一層的呢？最初的想法是用一個(gè) pair 再保存一個(gè)深度值，但是這樣有點(diǎn)多余了。

我們只需要每次隊(duì)列中只保存同一層的結(jié)點(diǎn)，然后記錄下隊(duì)列大小。然后依次出隊(duì)，直到出隊(duì)個(gè)數(shù)達(dá)到之前記錄的大小。并且同時(shí)將所有的下一層結(jié)點(diǎn)入隊(duì)。這樣就能保證這一層的結(jié)點(diǎn)全部出隊(duì)之后，隊(duì)列中只剩下了下一層的結(jié)點(diǎn)。

 

代碼

 

dfs（c++）

class Solution {public:    vector<int> rightSideView(TreeNode* root) {        if (!root) return {};        vector<int> left = rightSideView(root->left);        vector<int> right = rightSideView(root->right);        vector<int> res = {root->val};        for (auto x : right) res.push_back(x);        for (int i = right.size(), sz = left.size(); i < sz; ++i) {            res.push_back(left[i]);        }        return res;    }};
 
 

bfs（c++）

class Solution {public:    vector<int> rightSideView(TreeNode* root) {        vector<int> res;        queue<TreeNode*> Q;        if (root) Q.push(root);        while (!Q.empty()) {            int sz = Q.size();            while (sz--) {                TreeNode* node = Q.front();                Q.pop();                if (!sz) res.push_back(node->val);                if (node->left) Q.push(node->left);                if (node->right) Q.push(node->right);            }        }        return res;    }};

關(guān)于python二叉樹(shù)問(wèn)題的示例分析就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

分享文章：python二叉樹(shù)問(wèn)題的示例分析
文章位置：http://www.chinadenli.net/article16/gcccgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、云服務(wù)器、Google、網(wǎng)站制作、關(guān)鍵詞優(yōu)化、服務(wù)器托管

廣告

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

成都網(wǎng)站建設(shè)