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