面試熱點(diǎn)|二叉樹(shù)那點(diǎn)事兒
掃描二維碼
隨時(shí)隨地手機(jī)看文章
0x00.前言和雞湯
前面寫(xiě)了很多篇工程相關(guān)的文章，今天準(zhǔn)備寫(xiě)個(gè)數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的文章。
最近發(fā)現(xiàn)LeetCode的題目已經(jīng)1500+了，記得去年夏天的時(shí)候信誓旦旦說(shuō)每天刷一道一年也得幾百道了，果然沒(méi)過(guò)一星期這個(gè)flag就倒了，并且我看到了也沒(méi)有扶起來(lái)...
說(shuō)到底筆者還是個(gè)比較懶惰的人，畢竟人都是自然向下的，坐著不如倒著，舒適區(qū)雖然內(nèi)心慚愧但是要想走出來(lái)還是很難的，也算是應(yīng)了那句話(huà)：逃避雖可恥但很有用！
但是總有那么一個(gè)時(shí)刻無(wú)法忍受自己，那就勇敢地走出去，別回頭那種。
舉個(gè)栗子：回看筆者從15年畢業(yè)到之后的4年時(shí)間，存款沒(méi)有增長(zhǎng)多少，體重增速倒是很給力，終于那個(gè)點(diǎn)來(lái)了，自己不愿意做個(gè)胖子，那就跑步吧！就這樣從19年5月份開(kāi)始，經(jīng)歷了1km到3km到5km到10km到21km的過(guò)程，累計(jì)跑了1100km，心肺功能變強(qiáng)體重變輕，狀態(tài)也不一樣了，再回頭看看所謂的舒適區(qū)大概跟個(gè)狗窩差不多，所以無(wú)限風(fēng)光在險(xiǎn)峰 一點(diǎn)沒(méi)錯(cuò)，疫情之前最近的一次LSD：
圖:慶元旦業(yè)余自嗨跑20.19Km
筆者本碩都不是CS專(zhuān)業(yè)，相對(duì)來(lái)說(shuō)數(shù)據(jù)結(jié)構(gòu)和算法也一直都是短板，一直都是學(xué)了忘忘了學(xué)的怪圈，不過(guò)當(dāng)我們發(fā)自肺腑地決定去改變這個(gè)短板的時(shí)候，我們也就離數(shù)據(jù)結(jié)構(gòu)和算法強(qiáng)者不再遙遠(yuǎn)啦。
好了，雞湯也喝完了，本文將從3道二叉樹(shù)題目去嘗試歸納一些共性問(wèn)題，力爭(zhēng)讓我們快速獲得解題切入點(diǎn)，開(kāi)始吧！我們的征途是星辰大海！
圖：愛(ài)天文也愛(ài)磕鹽的師兄所拍獵戶(hù)座M42星云
0x01.一道面試題
這也是筆者遇到的一線(xiàn)大廠出的一道比較基礎(chǔ)的二叉樹(shù)面試題，之前并沒(méi)有做過(guò)，事后發(fā)現(xiàn)是leetcode的原題。
其實(shí)這個(gè)無(wú)所謂了，leetcode那么多題目，讓我去編題目我也可以，所以這個(gè)是沒(méi)有盡頭的，從這些題目中提煉歸納上升到屬于個(gè)人的心法和內(nèi)力才是王道。
看下這個(gè)題目描述(leetcode103題)：
給定一個(gè)二叉樹(shù)，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右，再?gòu)挠彝筮M(jìn)行下一層遍歷，以此類(lèi)推，層與層之間交替進(jìn)行）。
一圖勝千言：
相信很多讀者朋友都見(jiàn)過(guò)這道題目，沒(méi)錯(cuò) ，就是Z型變換遍歷。
1.1 思考一下
依稀記得筆者當(dāng)時(shí)面對(duì)這個(gè)題目棧和隊(duì)列弄了一堆，答得也不是很好，現(xiàn)在想一想是陷入細(xì)節(jié)了，這樣下去容易把自己繞暈。
現(xiàn)在從更宏觀的角度去看就是層次遍歷的一個(gè)變種問(wèn)題，在遍歷的過(guò)程中記住當(dāng)前的層索引編號(hào)來(lái)確定從左到右還是從右到左，但是這道題一直沒(méi)有動(dòng)手做，今天想起來(lái)了就做一下吧！
在做這道題之前，昨天晚上做了兩道Easy級(jí)別二叉樹(shù)的題目，在脈脈上有些大神說(shuō)做easy的題目還不如練練字，只能說(shuō)大神就是大神呀，比不了比不了，反正Easy的我也做的不少，如人飲水冷暖自知，起跑線(xiàn)不一樣，各自努力吧！
昨天做的兩道題目分別是(筆者做的樹(shù)的系列)：
LeetCode100題：
給定兩個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同。如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
LeetCode101題:
給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱(chēng)的。
只有題目做多了，我們才能從中提煉歸納，我們都知道二叉樹(shù)問(wèn)題大部分都是可以用遞歸來(lái)解決的，代碼簡(jiǎn)潔到蒙圈，像我這種不太靈光的，還是傾向于用迭代來(lái)實(shí)現(xiàn)，當(dāng)然最后還是會(huì)遞歸想一想，逃避不懂的知識(shí)點(diǎn)是不明智的。
1.2 一個(gè)插曲:我和立體幾何
筆者總是喜歡天馬行空，因?yàn)?/span>凡事都是相通的。
可能是因?yàn)榭臻g思維能力弱(囧)，所以有的事情總會(huì)讓我記憶猶新。
高二開(kāi)始學(xué)習(xí)立體幾何，具體的細(xì)節(jié)雖然記不清了，但是每次遇到題目就想起老師說(shuō)的各種技巧各種輔助線(xiàn)，最終磕磕絆絆也能做出來(lái)，當(dāng)然也有一些是完全沒(méi)有思路的，所以從那個(gè)時(shí)候起我喜歡解析幾何勝于立體幾何。
考試之后老師會(huì)板書(shū)講解，一聽(tīng)確實(shí)是那么回事，但是為啥當(dāng)時(shí)就想不到呢？深深懷疑著自己的笨腦袋，但是也沒(méi)辦法，硬鋼吧！
硬鋼的路上并不輕松，即使做出來(lái)也花費(fèi)很多時(shí)間，更多的是對(duì)此類(lèi)問(wèn)題的自信心逐漸減弱，這并不是個(gè)好現(xiàn)象，感受一下之前的題目：
沒(méi)關(guān)系，請(qǐng)相信世界依然美好，上帝關(guān)上了窗的時(shí)候大概率給我們留著門(mén)呢。
果然讓我找到了門(mén)，從我自己的角度去看，個(gè)人的解析計(jì)算能力是優(yōu)于立體空間思維的，那為啥不能空間幾何轉(zhuǎn)換為數(shù)值計(jì)算呢？
原來(lái)有一種技術(shù)叫空間坐標(biāo)系，這樣就可以把空間幾何的東西都坐標(biāo)化，進(jìn)而數(shù)值化，所以距離問(wèn)題、面積問(wèn)題、相交問(wèn)題、平行問(wèn)題等等都轉(zhuǎn)換為了數(shù)值計(jì)算問(wèn)題，深入學(xué)習(xí)了一段時(shí)間之后，自信心逐漸上來(lái)了，看到立體幾何的題目不敢說(shuō)庖丁解牛，最起碼也看個(gè)大概，就這樣立體幾何再也沒(méi)有成為我學(xué)習(xí)路上的攔路虎。
雖然這些事情已經(jīng)過(guò)去很久了，但是解決立體幾何問(wèn)題的這種心理活動(dòng)和現(xiàn)在做LeetCode上二叉樹(shù)的問(wèn)題很相似，一看題解貌似就是這么回事，一閉上題解，就不好下手(大囧)。
有時(shí)候，前進(jìn)路上唯一的攔路虎，不是別人，就是我們自己，僅此而已。
0x02.尋找二叉樹(shù)的門(mén)
不好意思前面又讓大家喝了一碗雞湯，現(xiàn)在準(zhǔn)備開(kāi)始啃雞腿了呦！
前面提到我是最近兩天做了3道二叉樹(shù)的問(wèn)題，發(fā)現(xiàn)了一些共性問(wèn)題，所以才決定寫(xiě)一寫(xiě)的，或許后面做了更多的題目會(huì)有更多的心得，所以大家持續(xù)關(guān)注吧！
首先聲明一點(diǎn)：筆者的迭代做法均不是最優(yōu)解，基本上在AC的時(shí)候被一大半的人從時(shí)間和空間打敗了，可能有人會(huì)問(wèn)那你還寫(xiě)它干啥？
筆者看來(lái)最優(yōu)解誠(chéng)可貴，但是很多時(shí)候在沒(méi)有見(jiàn)過(guò)題目，現(xiàn)場(chǎng)Coding時(shí)能有個(gè)正確的思路比啥都強(qiáng)，當(dāng)時(shí)ACM大神就另當(dāng)別論了，我們固然追求最優(yōu)解，多種嘗試解題，但是有個(gè)保底的通用思維也是雙保險(xiǎn)嘛，這也是本文的重點(diǎn)。
前面的三道題：兩棵相同的樹(shù)、一棵自成鏡像對(duì)稱(chēng)的樹(shù)、Z型遍歷樹(shù)，筆者除了用遞歸實(shí)現(xiàn)，最終都嘗試了一種迭代層次遍歷來(lái)解決，因?yàn)楸闅v對(duì)我們來(lái)說(shuō)更加容易，緊張場(chǎng)景下我們必然選擇自己熟悉的東西，來(lái)看下筆者在做這幾道題是的一些過(guò)程：
-
100題 兩棵相同的樹(shù)問(wèn)題
迭代層次遍歷，保留樹(shù)中的空節(jié)點(diǎn)，由于樹(shù)節(jié)點(diǎn)的值是int，為了區(qū)分空節(jié)點(diǎn)，統(tǒng)一轉(zhuǎn)換為string存儲(chǔ)，這樣一棵樹(shù)經(jīng)過(guò)轉(zhuǎn)換就成為了vector
-
101題 一棵鏡像的樹(shù)
這個(gè)還是采用迭代層次遍歷，int轉(zhuǎn)string 保存空節(jié)點(diǎn)為null存儲(chǔ)到vector
-
103題 鋸齒狀Z型遍歷樹(shù)
這個(gè)問(wèn)題和鏡像樹(shù)有些類(lèi)似，還是可以采用迭代分層遍歷，由于涉及到按照層編號(hào)來(lái)修改遍歷方向，因此需要做一些額外工作，對(duì)此筆者進(jìn)行了一個(gè)AC實(shí)現(xiàn)，但是我并不覺(jué)得這個(gè)是我想要的通用方法，所以我并沒(méi)有在遍歷過(guò)程中判斷層，因?yàn)樵跇?shù)上做其他操作容易讓我暈，索性遍歷存儲(chǔ)為vector
從上面的三道題可以看到，我均使用了迭代式層次遍歷，區(qū)別在于根據(jù)每道題的特性做了數(shù)組級(jí)別的調(diào)整，而不是樹(shù)級(jí)別的調(diào)整，我們知道數(shù)組更好理解也更好處理，這是個(gè)降維過(guò)程。
寫(xiě)到這里，仿佛有點(diǎn)意思了，所以再次重申本文不是找最優(yōu)解而是通用策略，目的是我們?cè)诿嬖噲?chǎng)上迅速找個(gè)一個(gè)可靠的解決方法，先實(shí)現(xiàn)再優(yōu)化和Offer更搭哦。
0x03.單挑Z型變換遍歷
Talk is Cheap,Show Me The Code!
3.1 Z型變換草稿
我們從我認(rèn)為更難一些的第103題來(lái)體驗(yàn)一下這個(gè)二叉樹(shù)的門(mén)，開(kāi)始我們的分析過(guò)程：
從一般到特殊的思維
二叉樹(shù)本身就是樹(shù)的一種簡(jiǎn)單特例，不是嗎？所以這個(gè)啟發(fā)很重要。
我們掌握規(guī)律更多的是完全二叉樹(shù)和滿(mǎn)二叉樹(shù)，所以我引入虛擬null節(jié)點(diǎn)讓普通樹(shù)變?yōu)橐?guī)律樹(shù)，其實(shí)引入虛擬節(jié)點(diǎn)這個(gè)套路在分布式一致性哈希的時(shí)候就用過(guò)，我們?yōu)楹尾粐L試一下呢？
從樹(shù)到數(shù)組的降維
仍舊以上圖的完全二叉樹(shù)為例進(jìn)行迭代層次遍歷并且將int轉(zhuǎn)換為string且存儲(chǔ)null節(jié)點(diǎn)，這樣整個(gè)二叉樹(shù)就成了這樣：[3,9,20,7,15,15,7,7,null,19,null]。
在遍歷過(guò)程中我們不好判斷null之后是否還會(huì)有其他非空節(jié)點(diǎn)，因此額外增加一個(gè)變量記錄迭代遍歷時(shí)隊(duì)列中的非null節(jié)點(diǎn)個(gè)數(shù)，當(dāng)隊(duì)列中沒(méi)有非空節(jié)點(diǎn)時(shí)遍歷就可以結(jié)束了，這樣我們存儲(chǔ)的二叉樹(shù)是沒(méi)有空洞的，這個(gè)很重要，后面代碼可以看到。
數(shù)組的處理
經(jīng)過(guò)上面幾個(gè)過(guò)程，我們初步達(dá)到了目標(biāo)，所以這個(gè)方案是行得通的，那么愉快地開(kāi)始編碼吧！
3.2 我的糙代碼
前面說(shuō)了，這個(gè)版本的代碼肯定不是最優(yōu)的，不過(guò)還是看下究竟有多粗糙和糟糕吧：
具體的代碼實(shí)現(xiàn)(未優(yōu)化版本)：
/**
* 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 {
public:
//處理每個(gè)層的數(shù)據(jù):將null清除 將string轉(zhuǎn)換為int 根據(jù)層數(shù)進(jìn)行翻轉(zhuǎn)
bool revseit(vector<string> &vec, int curlevl, vector<int> &res){
//由于層數(shù)是從1開(kāi)始編號(hào) 因此滿(mǎn)足奇數(shù)層從左到右不翻轉(zhuǎn) 偶數(shù)層翻轉(zhuǎn)為從右向左
vector<string>::iterator iter = vec.begin();
for(;iter!=vec.end();iter++){
if(*iter=="null")
continue;
res.push_back(std::stoi(*iter));
}
if(curlevl%2==0)
std::reverse(res.begin(),res.end());
return true;
}
//開(kāi)始處理由二叉樹(shù)構(gòu)造滿(mǎn)二叉樹(shù)生成的vector
bool dealit(vector<string> &vec, vector<vector<int> > &res){
//從頂向下按照滿(mǎn)二叉樹(shù)切割每層 每層結(jié)點(diǎn)數(shù)遵循 等比數(shù)列 1 2 4 8 .... 2^(k-1) k=1,2,3...
//滿(mǎn)二叉樹(shù)的總結(jié)點(diǎn)數(shù)量S=2^k-1 由此可以計(jì)算層數(shù) 也就是子vector的數(shù)量
int nodecnt = vec.size();
int levcnt = log(nodecnt+1)/log(2);
//這一步是判斷完全二叉樹(shù)的情況
bool notfull = false;
if(pow(2,levcnt)-1!=nodecnt){
notfull=true;
}
//我們從第1層開(kāi)始向后分層切割
int curlevl = 1;
vector<string> tmpvec;
vector<int> tmpsubres;
while(curlevl<=levcnt+1){
//臨時(shí)結(jié)構(gòu)清空
tmpvec.clear();
tmpsubres.clear();
//計(jì)算本層之前的全部結(jié)點(diǎn)數(shù)量 作為本次切片的起點(diǎn)
int lastsum = pow(2,curlevl-1)-1;
//計(jì)算本層的節(jié)點(diǎn)數(shù) 作為切片時(shí)的偏移量
int gap = pow(2,curlevl-1);
if(curlevl==levcnt+1){
if(notfull)
gap = nodecnt-lastsum;
else
break;
}
tmpvec.assign(vec.begin()+lastsum,vec.begin()+lastsum+gap);
revseit(tmpvec,curlevl,tmpsubres);
if(tmpsubres.size()>0)
res.push_back(tmpsubres);
curlevl++;
}
return true;
}
//非遞歸層次遍歷 注意空節(jié)點(diǎn)的處理
void travese(TreeNode *root, vector<string> &vec){
//相當(dāng)于一個(gè)標(biāo)記位 記錄隊(duì)列中非空節(jié)點(diǎn)數(shù)量
int oknodecnt = 0;
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
oknodecnt++;
while(!q.empty()&&oknodecnt>0)
{
TreeNode *top = q.front();
if(top){
//向隊(duì)列裝載左結(jié)點(diǎn)
if(top->left){
q.push(top->left);
oknodecnt++;
}else
q.push(NULL);
//向隊(duì)列裝載右節(jié)點(diǎn)
if(top->right){
q.push(top->right);
oknodecnt++;
}else
q.push(NULL);
//隊(duì)頭節(jié)點(diǎn)任務(wù)完成 可以彈出并加入到vector中
q.pop();
oknodecnt--;
vec.push_back(std::to_string(top->val));
}else{
//當(dāng)隊(duì)頭節(jié)點(diǎn)時(shí)NULL時(shí) 為了保證滿(mǎn)二叉樹(shù)的特性 向隊(duì)列中增加兩個(gè)NULL作為其虛擬孩子節(jié)點(diǎn)
q.pop();
q.push(NULL);
q.push(NULL);
vec.push_back("null");
}
}
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > res;
vector<string> vectree;
if(!root)
return res;
//層次遍歷
travese(root,vectree);
//處理遍歷后生成的vector
dealit(vectree,res);
return res;
}
};
其實(shí)筆者之所以這么繞地去實(shí)現(xiàn)一個(gè)問(wèn)題，也是為了由一道題練更多的知識(shí)點(diǎn)，代碼中的注釋寫(xiě)的還算詳細(xì)，感興趣的可以用web版的頁(yè)面查看，手機(jī)上閱讀體驗(yàn)差點(diǎn)意思。
0x04.其他兩道題目的糙代碼
對(duì)于LeetCode第100題相同的樹(shù)和LeetCode第101題鏡像樹(shù)，筆者均用相同的路子進(jìn)行解決，可以看下具體的實(shí)現(xiàn)。
4.1 第100題相同的樹(shù)
具體代碼：
/**
* 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 {
public:
//雖然該題目是easy 但是為了盡量多的練習(xí) 實(shí)用了非遞歸中序遍歷(包含空節(jié)點(diǎn))、vector、queue、迭代器的基本用法
void travese(TreeNode *root, vector<string> &vec)
{
//選擇非遞歸層次遍歷
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//左結(jié)點(diǎn)
if(top->left)
q.push(top->left);
else
q.push(NULL);
//右節(jié)點(diǎn)
if(top->right)
q.push(top->right);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
//遍歷vector對(duì)比
bool comp(vector<string> &vecp, vector<string> &vecq){
vector<string>::iterator iterp = vecp.begin();
vector<string>::iterator iterq = vecq.begin();
if(vecq.size()!=vecp.size())
return false;
for(;iterp!=vecp.end(),iterq!=vecq.end();iterp++,iterq++){
if(*iterp == *iterq)
continue;
else
return false;
}
return true;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q)
return true;
if(!q||!p)
return false;
//兩棵樹(shù)都非空的前提下
vector<string> vecp;
vector<string> vecq;
travese(p,vecp);
travese(q,vecq);
return comp(vecp,vecq);
}
};4.2 第101題鏡像樹(shù)
具體代碼：
/**
* 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 {
public:
//從左到右層次遍歷
void travese(TreeNode *root, vector<string> &vec)
{
//選擇非遞歸層次遍歷
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//左結(jié)點(diǎn)
if(top->left)
q.push(top->left);
else
q.push(NULL);
//右節(jié)點(diǎn)
if(top->right)
q.push(top->right);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
//從右到左層次遍歷
void revtravese(TreeNode *root, vector<string> &vec)
{
//選擇非遞歸層次遍歷
TreeNode *node = root;
queue<TreeNode*> q;
q.push(node);
while(!q.empty())
{
TreeNode *top = q.front();
if(top){
//右結(jié)點(diǎn)
if(top->right)
q.push(top->right);
else
q.push(NULL);
//左節(jié)點(diǎn)
if(top->left)
q.push(top->left);
else
q.push(NULL);
q.pop();
vec.push_back(std::to_string(top->val));
}else{
q.pop();
vec.push_back("null");
}
}
}
bool isSymmetric(TreeNode* root) {
//空樹(shù)或者只有根節(jié)點(diǎn)的樹(shù)
if(!root||(root->left==NULL&&root->right==NULL))
return true;
//其他情況
vector<string> vecleft;
vector<string> vecright;
travese(root,vecleft);
revtravese(root,vecright);
return vecleft==vecright;
}
};0x05.筆者小結(jié)
寫(xiě)到這里基本上就到尾聲了，簡(jiǎn)單總結(jié)一下：
本文通過(guò)3道二叉樹(shù)的問(wèn)題展開(kāi)，目前是讓我們獲得一種在緊張場(chǎng)合快速切入解題的思路，其中涉及到一些自己的習(xí)慣可能并不為很多人接受，其次筆者本著一道題復(fù)習(xí)多個(gè)知識(shí)點(diǎn)的原則實(shí)現(xiàn)了很長(zhǎng)的代碼，無(wú)他就是為了練習(xí)。
做LeetCode就像現(xiàn)在手機(jī)廠商發(fā)布會(huì)上跑個(gè)分看看，亮一亮?xí)r間和空間碾壓了多少人，漂亮簡(jiǎn)潔的算法確實(shí)讓人驚艷，但是其背后凝結(jié)了無(wú)數(shù)的糙代碼。
道阻且長(zhǎng) 戒驕戒躁 扎好馬步 我們也可以練就九陽(yáng)神功！
點(diǎn)【在看】是最大的支持
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
