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