【文章內(nèi)容簡介】 L) { }}。*/class Solution { public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){ if(pRoot1==NULL || pRoot2==NULL) return false。 return isSubtree(pRoot1,pRoot2)。 } bool isSubtree(TreeNode *pa, TreeNode *pb){ if(pa==NULL) return false。//遞歸結(jié)束條件 bool ret = false。//返回值 if(paval==pbval) ret = isSubtreeTmp(pa,pb)。//節(jié)點(diǎn)值相同，繼續(xù)判斷左右子樹 if(ret) return true。//如果左右子樹都相同，表示已找到，立即返回 ret = isSubtree(paleft,pb)。//節(jié)點(diǎn)值不相同，在A樹的左子樹中尋找 if(ret) return true。//如果找到，立即返回 ret = isSubtree(paright,pb)。//節(jié)點(diǎn)值不相同，在B樹的右子樹中尋找 if(ret) return true。//如果找到，立即返回 else return false。//上述都找不到時(shí)，返回false } bool isSubtreeTmp(TreeNode *pa, TreeNode *pb){ if(pb==NULL) return true。//為空，說明此子樹已完全匹配 if(pa==NULL amp。amp。 pb!=NULL) return false。//如果A樹先空，而B樹還沒空，匹配失敗 return paval==pbval amp。amp。 isSubtreeTmp(paleft,pbleft) amp。amp。 isSubtreeTmp(paright,pbright)。//如果節(jié)點(diǎn)值相同，繼續(xù)匹配左子樹和右子樹 }}。分析：這題主要是搞清楚子結(jié)構(gòu)的定義。思路：先序遍歷每一個(gè)節(jié)點(diǎn)，從A樹根節(jié)點(diǎn)開始判斷：1）當(dāng)前節(jié)點(diǎn)的值與B樹根節(jié)點(diǎn)的值是否一樣，若一樣，執(zhí)行2）；否則，執(zhí)行3）；2）繼續(xù)判斷A樹左子樹和B樹左子樹，以及A樹右子樹和B樹右子樹；3）說明此節(jié)點(diǎn)一定不是子結(jié)構(gòu)的根節(jié)點(diǎn)，則： ）遞歸：令當(dāng)前節(jié)點(diǎn)的左孩子為當(dāng)前節(jié)點(diǎn)，執(zhí)行1）； ）遞歸：令當(dāng)前節(jié)點(diǎn)的右孩子為當(dāng)前節(jié)點(diǎn)，執(zhí)行1）；函數(shù)isSubtree中有很多return語句，主要是為了在找到子結(jié)構(gòu)時(shí)能夠立即返回，避免不必要的遞歸。本題的“子結(jié)構(gòu)”需要注意以下幾點(diǎn)：1）節(jié)點(diǎn)值可以重復(fù)；2）樹B只是樹A的一部分，不一定非要到葉子節(jié)點(diǎn)，即下面的情況是滿足子結(jié)構(gòu)的： 2 2 2 3 4 5 4 5 B樹 6 7 A樹3）當(dāng)樹A不空、B樹空時(shí)，B樹也是A樹的子結(jié)構(gòu)。l 二叉樹的鏡像操作給定的二叉樹，將其變換為源二叉樹的鏡像。二叉樹的鏡像定義：源二叉樹 8 / \ 6 10 / \ / \ 5 7 9 11 鏡像二叉樹 8 / \ 10 6 / \ / \ 11 9 7 5代碼：/*struct TreeNode { int val。 struct TreeNode *left。 struct TreeNode *right。 TreeNode(int x) : val(x), left(NULL), right(NULL) { }}。*/class Solution {public: void Mirror(TreeNode *pRoot) { if(pRoot==NULL) return。 TreeNode *node = pRootleft。 pRootleft = pRootright。 pRootright = node。 Mirror(pRootleft)。 Mirror(pRootright)。 }}。分析：遞歸地交換左右子樹即可。l 順時(shí)針打印矩陣輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.本題代碼分成兩步來說：第一步：class Solution {public: vectorint printMatrix(vectorvectorint matrix) { vectorint vec。 int row = ()。//行數(shù) int col = matrix[0].size()。//列數(shù) int k = 0。//控制循環(huán)輸出的次數(shù) while(k=row/2 amp。amp。 k=col/2){ int i = k, j = k。//每一次循環(huán)輸出從matrix[k][k]開始 while(jcolk) (matrix[i][j++])。//從“左上角向右上角”輸出 j。i++。//j—因?yàn)樯厦鎤hile多加了1；i++走向下一行 while(irowk) (matrix[i++][j])。//從“右上角向右下角”輸出 i。j。//i—因?yàn)樯厦鎤hile多加了1；j—走向左一列 while(j=k) (matrix[i][j])。//從“右下角向左下角”輸出 j++。i。//j++因?yàn)樯厦鎤hile多減了1；i—走向上一行 while(i=k+1) (matrix[i][j])。//從“左下角向左上角”輸出 k++。//準(zhǔn)備進(jìn)行下一輪 } return vec。 }}。分析：一圈可以分成四步：1）從左上角到右上角2）從右上角到右下角3）從右下角到左下角4）從左下角到左上角只要控制好每次輸出的起點(diǎn)和終點(diǎn)即可：1）從左上角到右上角的起點(diǎn)~終點(diǎn)：[k,k]~[k,colk1]2）從右上角到右下角的起點(diǎn)~終點(diǎn)：[k+1,colk1]~[rowk1,colk1]3）從右下角到左下角的起點(diǎn)~終點(diǎn)：[rowk1,colk2] ~[rowk1,k]4）從左下角到左上角的起點(diǎn)~終點(diǎn)：[rowk2,k]~[k+2,k]其中的i，j就是在起點(diǎn)和終點(diǎn)之間不斷地變換。來研究下k的取值范圍，需要考慮多種特殊情況：（1）row=0，col=0，即行數(shù)和列數(shù)都是0；（2）row=1或者col=1，即只有一行，或只有一列；（3）row!=col，即矩陣不是方陣，這種情況比較普遍；（4）每次k從主對角線依次開始，一圈之后，會(huì)輸出兩行、兩列；我們希望通過k的取值，把這些情況都包含進(jìn)去：（1）和（2）通過 “=”來表達(dá)（3）通過 “amp。amp。”來表達(dá)；（4）通過“row/2”和“col/2”來表達(dá)；所以綜合起來，主循環(huán)條件就是：k=row/2 amp。amp。 k=col/2上述代碼能夠保證不會(huì)少輸出元素，但是很多情況會(huì)多輸出元素，即某些元素被重復(fù)輸出了。為了解決這個(gè)問題，需要加上下面幾句：第二步：class Solution {public: vectorint printMatrix(vectorvectorint matrix) { vectorint vec。 int row = ()。 int col = matrix[0].size()。 int k = 0。 while(k=row/2 amp。amp。 k=col/2){ int i = k, j = k。 if(i=rowk) break。//(1) while(jcolk) (matrix[i][j++])。 j。i++。 if(jk) break。//(2) while(irowk) (matrix[i++][j])。 i。j。 if(i=k) break。//(3) while(j=k) (matrix[i][j])。 j++。i。 if(j=colk1) break。//(4) while(i=k+1) (matrix[i][j])。 k++。 } return vec。 }}。紅色部分就是為了避免重復(fù)輸出的，下面依次分析：（1）這是為了防止重復(fù)上一輪循環(huán)中輸出的元素。想想看，上一輪循環(huán)中，輸出的最大一行（行數(shù)最大）是第rowk1行（這里的k是上一輪的k）。到了這一輪，我們要保證不能輸出比第rowk1還大的行，因?yàn)槟切┒际侵拜喆屋敵鲞^的。這一輪的k比上一輪的k大1，所以此輪中只要i=rowk，說明此第i行已經(jīng)上上一輪輸出過了。一旦出現(xiàn)這種情況，立馬跳出主循環(huán)。（2）也是為了防止重復(fù)輸出上一輪循環(huán)中輸出的元素。上一輪中輸出的最小列是第k列（上一輪的k），這一輪輸出的列不能小于上一輪的第k列。所以jk（此輪的k）不能出現(xiàn)。（3）防止這一輪剛才輸出的行再次被輸出。剛才輸出的行（第k行）是從左上角到右上角，現(xiàn)在要輸出的行（第i行）是右下角到左下角，那么這兩行不能重復(fù)輸出吧！所以不能i=k。（4）防止這一輪剛才輸出的列再次被輸出。剛才輸出的列（第colk1列）是從右上角到右下角，現(xiàn)在要輸出的列（第j列）是從左下角到左上角，那么這兩行也不能重復(fù)輸出吧！所以不能j=colk1。好了，經(jīng)過上面四個(gè)“避免重復(fù)”，缺一不可，然后此題可以AC了。上述講解過程可能不太容易理解，但看的出來有很強(qiáng)的規(guī)律性，且代碼簡潔。主循環(huán)里面的四個(gè)小循環(huán)，每個(gè)小循環(huán)都是先計(jì)算好起點(diǎn)，然后判斷是否會(huì)重復(fù)輸出，最后再輸出。一旦發(fā)現(xiàn)會(huì)重復(fù)輸出，立馬結(jié)束主循環(huán)。l 包含min函數(shù)的棧定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。代碼：class Solution { vectorint vec。public: void push(int value) { (value)。 } void pop() { ()。 } int top() { return (()1)。 } int min() { int size = ()。 if(size==1) return (0)。 int min = (0)。 for(int i=1。isize。i++) if((i)min) min = (i)。 return min。 }}。分析：此題本意在用兩個(gè)棧，一個(gè)棧m_data用于存放數(shù)據(jù)，另一個(gè)棧m_min用于存放當(dāng)前最小值。比如：1）插入3時(shí)，3是當(dāng)前最小值，(3)。(3)。 兩者同時(shí)插入元素。只不過m_min插入的永遠(yuǎn)是當(dāng)前最小值。2）插入4時(shí)，3還是當(dāng)前的最小值，(4)。(3)。3）插入2時(shí)，2是當(dāng)前最小值，(2)。(2)。4）插入1時(shí)，1是當(dāng)前最小值，(1)。(1)。5）獲取當(dāng)前最小值，則直接取m_min棧頂元素即可，()。6）彈出1時(shí)，()。()。 兩者同時(shí)彈出棧頂元素《劍指offer》上是這樣寫的，明顯是以空間換時(shí)間的方法。而我沒這樣寫，我的是用一個(gè)vector來保存元素，當(dāng)獲取最小值時(shí)，遍歷vector獲得最小值，時(shí)間復(fù)雜度為O(N)，N為棧中元素個(gè)數(shù)。l 棧的壓入、彈出序列輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。代碼：class Solution {public: