給「代碼隨想錄」一個星標吧！?

有學習就要有總結

?

本周小結

本周趕上了十一國慶，估計大家已經對本周末沒什么概念了，但是我們該做總結還是要做總結的。

本周的主題其實是「簡單但并不簡單」，本周所選的題目大多是看一下就會的題目，但是大家看完本周的文章估計也發現了，二叉樹的簡答題目其實里面都藏了很多細節。這些細節我都給大家展現了出來。

周一

本周剛開始我們講解了判斷二叉樹是否對稱的寫法， 二叉樹：我對稱么？。

這道題目的本質是要比較兩個樹(這兩個樹是根節點的左右子樹)，遍歷兩棵樹而且要比較內側和外側節點，所以準確的來說是一個樹的遍歷順序是左右中，一個樹的遍歷順序是右左中。

而本題的迭代法中我們使用了隊列，需要注意的是這不是層序遍歷，而且僅僅通過一個容器來成對的存放我們要比較的元素，認識到這一點之后就發現：用隊列，用棧，甚至用數組，都是可以的。

那么做完本題之后，再看如下兩個題目。

• 100.相同的樹
• 572.另一個樹的子樹

「二叉樹：我對稱么？中的遞歸法和迭代法只需要稍作修改其中一個樹的遍歷順序，便可刷了100.相同的樹。」

100.相同的樹的遞歸代碼如下：

class?Solution?{
public:
????bool?compare(TreeNode*?left,?TreeNode*?right)?{
????????//?首先排除空節點的情況
????????if?(left?==?NULL?&&?right?!=?NULL)?return?false;
????????else?if?(left?!=?NULL?&&?right?==?NULL)?return?false;
????????else?if?(left?==?NULL?&&?right?==?NULL)?return?true;
????????//?排除了空節點，再排除數值不相同的情況
????????else?if?(left->val?!=?right->val)?return?false;

????????//?此時就是：左右節點都不為空，且數值相同的情況
????????//?此時才做遞歸，做下一層的判斷
??????? bool outside = compare(left->left, right->right);???//?左子樹：左、?右子樹：左?(相對于求對稱二叉樹，只需改一下這里的順序)
??????? bool inside = compare(left->right, right->left);????//?左子樹：右、?右子樹：右
??????? bool isSame = outside && inside;????????????????????//?左子樹：中、?右子樹：中?(邏輯處理)
????????return?isSame;

????}
????bool?isSymmetric(TreeNode*?root)?{
????????if?(root?==?NULL)?return?true;
????????return?compare(root->left,?root->right);
????}
};

100.相同的樹，精簡之后代碼如下：

class?Solution?{
public:
????bool?compare(TreeNode*?left,?TreeNode*?right)?{
????????if?(left?==?NULL?&&?right?!=?NULL)?return?false;
????????else?if?(left?!=?NULL?&&?right?==?NULL)?return?false;
????????else?if?(left?==?NULL?&&?right?==?NULL)?return?true;
????????else?if?(left->val?!=?right->val)?return?false;
????????else?return?compare(left->left,?right->left)?&&?compare(left->right,?right->right);

????}
????bool?isSameTree(TreeNode*?p,?TreeNode*?q)?{
????????return?compare(p,?q);
????}
};

100.相同的樹，迭代法代碼如下：

lass?Solution?{
public:

????bool?isSameTree(TreeNode*?p,?TreeNode*?q)?{
????????if?(p?==?NULL?&&?q?==?NULL)?return?true;
????????if?(p?==?NULL?||?q?==?NULL)?return?false;
????????queue?que;
????????que.push(p);???
????????que.push(q);??while?(!que.empty())?{??
????????????TreeNode*?leftNode?=?que.front();?que.pop();
????????????TreeNode*?rightNode?=?que.front();?que.pop();if?(!leftNode?&&?!rightNode)?{??continue;
????????????}if?((!leftNode?||?!rightNode?||?(leftNode->val?!=?rightNode->val)))?{return?false;
????????????}
????????????//?相對于求對稱二叉樹，這里兩個樹都要保持一樣的遍歷順序
????????????que.push(leftNode->left);?
????????????que.push(rightNode->left);?
????????????que.push(leftNode->right);??
????????????que.push(rightNode->right);??
????????}return?true;
????}
};

而572.另一個樹的子樹，則和 100.相同的樹幾乎一樣的了，大家可以直接AC了。

周二

在二叉樹：看看這些樹的最大深度中，我們講解了如何求二叉樹的最大深度。

本題可以使用前序，也可以使用后序遍歷(左右中)，使用前序求的就是深度，使用后序呢求的是高度。

「而根節點的高度就是二叉樹的最大深度」，所以本題中我們通過后序求的根節點高度來求的二叉樹最大深度，所以二叉樹：看看這些樹的最大深度中使用的是后序遍歷。

本題當然也可以使用前序，代碼如下：(「充分表現出求深度回溯的過程」)

class?Solution?{
public:
????int?result;
????void?getDepth(TreeNode*?node,?int?depth)?{
????????result?=?depth?>?result???depth?:?result;?//?中

????????if?(node->left?==?NULL?&&?node->right?==?NULL)?return?;

????????if?(node->left)?{?//?左
????????????depth++;????//?深度+1
????????????getDepth(node->left,?depth);
????????????depth--;????//?回溯，深度-1
????????}
????????if?(node->right)?{?//?右
????????????depth++;????//?深度+1
????????????getDepth(node->right,?depth);
????????????depth--;????//?回溯，深度-1
????????}
????????return?;
????}
????int?maxDepth(TreeNode*?root)?{
????????result?=?0;
????????if?(root?==?0)?return?result;
????????getDepth(root,?1);
????????return?result;
????}
};

「可以看出使用了前序(中左右)的遍歷順序，這才是真正求深度的邏輯！」

注意以上代碼是為了把細節體現出來，簡化一下代碼如下：

class?Solution?{
public:
????int?result;
????void?getDepth(TreeNode*?node,?int?depth)?{
????????result?=?depth?>?result???depth?:?result;?//?中
????????if?(node->left?==?NULL?&&?node->right?==?NULL)?return?;
????????if?(node->left)?{?//?左
????????????getDepth(node->left,?depth?+?1);
????????}
????????if?(node->right)?{?//?右
????????????getDepth(node->right,?depth?+?1);
????????}
????????return?;
????}
????int?maxDepth(TreeNode*?root)?{
????????result?=?0;
????????if?(root?==?0)?return?result;
????????getDepth(root,?1);
????????return?result;
????}
};

周三

在二叉樹：看看這些樹的最小深度中，我們講解如何求二叉樹的最小深度， 這道題目要是稍不留心很容易犯錯。

「注意這里最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。注意是葉子節點。」

什么是葉子節點，左右孩子都為空的節點才是葉子節點！

「求二叉樹的最小深度和求二叉樹的最大深度的差別主要在于處理左右孩子不為空的邏輯。」

注意到這一點之后 遞歸法和迭代法 都可以參照二叉樹：看看這些樹的最大深度寫出來。

周四

我們在二叉樹：我有多少個節點？中，講解了如何求二叉樹的節點數量。

這一天是十一長假的第一天，又是雙節，所以簡單一些，只要把之前兩篇二叉樹：看看這些樹的最大深度， 二叉樹：看看這些樹的最小深度都認真看了的話，這道題目可以分分鐘刷掉了。

估計此時大家對這一類求二叉樹節點數量以及求深度應該非常熟練了。

周五

在二叉樹：我平衡么？中講解了如何判斷二叉樹是否是平衡二叉樹

今天講解一道判斷平衡二叉樹的題目，其實 方法上我們之前講解深度的時候都講過了，但是這次我們通過這道題目徹底搞清楚二叉樹高度與深度的問題，以及對應的遍歷方式。

二叉樹節點的深度：指從根節點到該節點的最長簡單路徑邊的條數。二叉樹節點的高度：指從該節點到葉子節點的最長簡單路徑邊的條數。

「但leetcode中強調的深度和高度很明顯是按照節點來計算的」。

關于根節點的深度究竟是1 還是 0，不同的地方有不一樣的標準，leetcode的題目中都是以節點為一度，即根節點深度是1。但維基百科上定義用邊為一度，即根節點的深度是0，我們暫時以leetcode為準(畢竟要在這上面刷題)。

當然此題用迭代法，其實效率很低，因為沒有很好的模擬回溯的過程，所以迭代法有很多重復的計算。

雖然理論上所有的遞歸都可以用迭代來實現，但是有的場景難度可能比較大。

「例如：都知道回溯法其實就是遞歸，但是很少人用迭代的方式去實現回溯算法！」

講了這么多二叉樹題目的迭代法，有的同學會疑惑，迭代法中究竟什么時候用隊列，什么時候用棧？

「如果是模擬前中后序遍歷就用棧，如果是適合層序遍歷就用隊列，當然還是其他情況，那么就是 先用隊列試試行不行，不行就用棧。」

周六

在二叉樹：找我的所有路徑？中正式涉及到了回溯，很多同學過了這道題目，可能都不知道自己使用了回溯，其實回溯和遞歸都是相伴相生的。最后我依然給出了迭代法的版本。

我在題解中第一個版本的代碼會把回溯的過程充分體現出來，如果大家直接看簡潔的代碼版本，很可能就會忽略的回溯的存在。

我在文中也強調了這一點。

有的同學還不理解 ，文中精簡之后的遞歸代碼，回溯究竟隱藏在哪里了。

文中我明確的說了：「回溯就隱藏在traversal(cur->left, path + "->", result);中的 path + "->"。每次函數調用完，path依然是沒有加上"->" 的，這就是回溯了。」

如果還不理解的話，可以把

traversal(cur->left,?path?+?"->",?result);

改成

string?tmp?=?path?+?"->";
traversal(cur->left,?tmp,?result);

看看還行不行了，答案是這么寫就不行了，因為沒有回溯了。

總結

二叉樹的題目，我都是使用了遞歸三部曲一步一步的把整個過程分析出來，而不是上來就給出簡潔的代碼。

一些同學可能上來就能寫出代碼，大體上也知道是為啥，可以自圓其說，但往細節一扣，就不知道了。

所以剛接觸二叉樹的同學，建議按照文章分析的步驟一步一步來，不要上來就照著精簡的代碼寫(那樣寫完了也很容易忘的，知其然不知其所以然)。

「簡短的代碼看不出遍歷的順序，也看不出分析的邏輯，還會把必要的回溯的邏輯隱藏了，所以盡量按照原理分析一步一步來，寫出來之后，再去優化代碼。」

下周依然是二叉樹，大家加個油！！

在留言區留下你的思路吧！

-------end-------

我將算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，里面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖看一看一定會有所收獲，如果給你有幫助給一個star支持一下吧！

另外因為公眾號改版，時間線被打亂，一些精彩文章大家可能錯過了。如果感覺這里的文章對你有幫助，趕緊給「代碼隨想錄」加一個星標吧，方便第一時間閱讀文章。往期精彩回顧二叉樹：找我的所有路徑？二叉樹：我平衡么？二叉樹：我有多少個節點？二叉樹：看看這些樹的最小深度二叉樹：看看這些樹的最大深度二叉樹：我對稱么？本周小結！(二叉樹)二叉樹：你真的會翻轉二叉樹么？二叉樹：層序遍歷登場！二叉樹：前中后序迭代方式的寫法就不能統一一下么？二叉樹：聽說遞歸能做的，棧也能做！二叉樹：一入遞歸深似海，從此offer是路人關于二叉樹，你該了解這些！「代碼隨想錄」期待你的關注！

每天8:35準時推送一道經典算法題目，推送的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理算法知識脈絡，輕松學算法！

刷題可以加我微信！右邊為個人微信，添加時備注：「簡單自我介紹」+「組隊刷題」我就知道你[在看]

總結

以上是生活随笔為你收集整理的求二叉树中以x为根的子树的深度_还在玩耍的你，该总结啦！（本周小结之二叉树）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。