操影视,北条麻妃成人视频,翔田千里菊门无码,色婷婷aⅴ,大香蕉123,天天干天天操天天,夏目あきら被续侵犯7天,国产资源av

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?建立四叉樹，我們先來看題面：

https://leetcode-cn.com/problems/construct-quad-tree/

示例

解題

https://blog.csdn.net/zrh_CSDN/article/details/84140253

解題思路：

我們想要使用一棵四叉樹來儲存一個?N x N?的布爾值網(wǎng)絡(luò)。網(wǎng)絡(luò)中每一格的值只會是真或假。樹的根結(jié)點代表整個網(wǎng)絡(luò)。對于每個結(jié)點, 它將被分等成四個孩子結(jié)點直到這個區(qū)域內(nèi)的值都是相同的。

每個結(jié)點還有另外兩個布爾變量:?isLeaf?和?val。isLeaf?當(dāng)這個節(jié)點是一個葉子結(jié)點時為真。val?變量儲存葉子結(jié)點所代表的區(qū)域的值。

你的任務(wù)是使用一個四叉樹表示給定的網(wǎng)絡(luò)。下面的例子將有助于你理解這個問題：

給定下面這個8 x 8?網(wǎng)絡(luò)，我們將這樣建立一個對應(yīng)的四叉樹：

由上文的定義，它能被這樣分割：

對應(yīng)的四叉樹應(yīng)該像下面這樣，每個結(jié)點由一對?(isLeaf, val)?所代表.

對于非葉子結(jié)點，val?可以是任意的，所以使用*代替。

提示：

N?將小于?1000?且確保是 2 的整次冪。
如果你想了解更多關(guān)于四叉樹的知識，你可以參考這個 wiki 頁面。

class?Solution?{
public:
????Node* construct(vector<vector<int>>& grid)?{
????????int?m = grid.size();
????????// cout<
????????if(m == 0){
????????????return?NULL;
????????}else?if(m == 1){
????????????if(grid[0][0] == 1){
????????????????return?new?Node(true, true, NULL, NULL, NULL, NULL);
????????????}else{
????????????????return?new?Node(false, true, NULL, NULL, NULL, NULL);
????????????}
????????}else{
????????????vector<vector<int>> lt; // left top
????????????vector<vector<int>> rt; // right top
????????????vector<vector<int>> lb; // left bottom
????????????vector<vector<int>> rb; //right bottom
????????????int?half = m/2;
????????????for(int?i = 0; i < half; i++){
????????????????lt.push_back(vector<int>(grid[i].begin(), grid[i].begin() + half));
????????????????lb.push_back(vector<int>(grid[i+half].begin(), grid[i+half].begin() + half));
????????????????rt.push_back(vector<int>(grid[i].begin()+half, grid[i].end()));
????????????????rb.push_back(vector<int>(grid[i+half].begin()+half, grid[i+half].end()));
????????????}
????????????Node* _lt = construct(lt);
????????????Node* _rt = construct(rt);
????????????Node* _lb = construct(lb);
????????????Node* _rb = construct(rb);
????????????if(_lt->isLeaf && _rt->isLeaf && _lb->isLeaf && _rb->isLeaf){
????????????????if(_lt->val && _rt->val && _lb->val && _rb->val){
????????????????????return?new?Node(true, true, NULL, NULL, NULL, NULL);
????????????????}else?if(!_lt->val && !_rt->val && !_lb->val && !_rb->val){
????????????????????return?new?Node(false, true, NULL, NULL, NULL, NULL);
????????????????}else{
????????????????????return?new?Node(false, false, _lt, _rt, _lb, _rb);
????????????????}
????????????}else{
????????????????return?new?Node(false, false, _lt, _rt, _lb, _rb);
????????????}
????????}
????}
};

好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。

上期推文：

LeetCode1-420題匯總，希望對你有點幫助！

LeetCode刷題實戰(zhàn)421：數(shù)組中兩個數(shù)的最大異或值

LeetCode刷題實戰(zhàn)422：有效的單詞方塊

LeetCode刷題實戰(zhàn)423：從英文中重建數(shù)字

LeetCode刷題實戰(zhàn)424：替換后的最長重復(fù)字符

LeetCode刷題實戰(zhàn)425：單詞方塊

LeetCode刷題實戰(zhàn)426：將二叉搜索樹轉(zhuǎn)化為排序的雙向鏈表

?LeetCode刷題實戰(zhàn)427：建立四叉樹

示例

解題