以後每周加上一個本周小結怎麼樣？
❞本周小結發現大家周末的時候貌似都不在學習狀態，周末的文章瀏覽量和打卡情況照工作日差很多呀，可能是本周日是工作日了，周六得好好放鬆放鬆，哈哈，理解理解，但我還不能不更啊，還有同學要看呢。
所以呢，「周日我做一個針對本周的打卡留言疑問以及在刷題群裡的討論內容做一下梳理吧。」，這樣也有助於大家補一補本周的內容，消化消化。
「注意這個周末總結和系列總結還是不一樣的（二叉樹還遠沒有結束），這個總結是針對留言疑問以及刷題群裡討論內容的歸納。」
周一本周我們開始講解了二叉樹，在關於二叉樹，你該了解這些！中講解了二叉樹的理論基礎。
有同學會把紅黑樹和二叉平衡搜索樹弄分開了，其實紅黑樹就是一種二叉平衡搜索樹，這兩個樹不是獨立的，所以C++中map、multimap、set、multiset的底層實現機制是二叉平衡搜索樹，再具體一點是紅黑樹。
對於二叉樹節點的定義，C++代碼如下：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
對於這個定義中TreeNode(int x) : val(x), left(NULL), right(NULL) {} 有同學不清楚幹什麼的。
這是構造函數，這麼說吧C語言中的結構體是C++中類的祖先，所以C++結構體也可以有構造函數。
構造函數也可以不寫，但是new一個新的節點的時候就比較麻煩。
例如有構造函數，定義初始值為9的節點：
TreeNode* a = new TreeNode(9);
沒有構造函數的話就要這麼寫：
TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;
在介紹前中後序遍歷的時候，有遞歸和迭代（非遞歸），還有一種牛逼的遍歷方式：morris遍歷。
morris遍歷是二叉樹遍歷算法的超強進階算法，morris遍歷可以將非遞歸遍歷中的空間複雜度降為O(1)，感興趣大家就去查一查學習學習，比較小眾，面試幾乎不會考。我其實也沒有研究過，就不做過多介紹了。
周二在二叉樹：一入遞歸深似海，從此offer是路人中講到了遞歸三要素，以及前中後序的遞歸寫法。
文章中我給出了leetcode上三道二叉樹的前中後序題目，但是看完二叉樹：一入遞歸深似海，從此offer是路人，依然可以解決n叉樹的前後序遍歷，在leetcode上分別是
大家可以再去把這兩道題目做了。
周三在二叉樹：聽說遞歸能做的，棧也能做！中我們開始用棧來實現遞歸的寫法，也就是所謂的迭代法。
細心的同學發現文中前後序遍歷空節點是入棧的，其實空節點入不入棧都差不多，但感覺空節點不入棧確實清晰一些，符合文中動畫的演示。
前序遍歷空節點不入棧的代碼：（注意注釋部分，和文章中的區別）
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空節點不入棧）
if (node->left) st.push(node->left); // 左（空節點不入棧）
}
return result;
}
};
後序遍歷空節點不入棧的代碼：（注意注釋部分，和文章中的區別）
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 相對於前序遍歷，這更改一下入棧順序 （空節點不入棧）
if (node->right) st.push(node->right); // 空節點不入棧
}
reverse(result.begin(), result.end()); // 將結果反轉之後就是左右中的順序了
return result;
}
};
在實現迭代法的過程中，有同學問了：遞歸與迭代究竟誰優誰劣呢？
從時間複雜度上其實迭代法和遞歸法差不多（在不考慮函數調用開銷和函數調用產生的堆棧開銷），但是空間複雜度上，遞歸開銷會大一些，因為遞歸需要系統堆棧存參數返回值等等。
遞歸更容易讓程式設計師理解，但收斂不好，容易棧溢出。
這麼說吧，遞歸是方便了程式設計師，難為了機器（各種保存參數，各種進棧出棧）。
「在實際項目開發的過程中我們是要儘量避免遞歸！因為項目代碼參數、調用關係都比較複雜，不容易控制遞歸深度，甚至會棧溢出。」
周四在二叉樹：前中後序迭代方式的寫法就不能統一一下麼？中我們使用空節點作為標記，給出了統一的前中後序迭代法。
此時又多了一種前中後序的迭代寫法，那麼有同學問了：前中後序迭代法是不是一定要統一來寫，這樣才算是規範。
其實沒必要，還是自己感覺哪一種更好記就用哪種。
但是「一定要掌握前中後序一種迭代的寫法，並不因為某種場景的題目一定要用迭代，而是現場面試的時候，面試官看你順暢的寫出了遞歸，一般會進一步考察能不能寫出相應的迭代。」
周五在二叉樹：層序遍歷登場！中我們介紹了二叉樹的另一種遍歷方式（圖論中廣度優先搜索在二叉樹上的應用）即：層序遍歷。
看完這篇文章，去leetcode上怒刷五題，文章中 編號107題目的樣例圖放錯了（原諒我匆忙之間總是手抖），但不影響大家理解。
只有同學發現leetcode上「515. 在每個樹行中找最大值」，也是層序遍歷的應用，依然可以分分鐘解決，所以就是一鼓作氣解決六道了，哈哈。
「層序遍歷遍歷相對容易一些，只要掌握基本寫法（也就是框架模板），剩下的就是在二叉樹每一行遍歷的時候做做邏輯修改。」
周六在二叉樹：你真的會翻轉二叉樹麼？中我們把翻轉二叉樹這麼一道簡單又經典的問題，充分的剖析了一波，相信就算做過這道題目的同學，看完本篇之後依然有所收穫！
「文中我指的是遞歸的中序遍歷是不行的，因為使用遞歸的中序遍歷，某些節點的左右孩子會翻轉兩次。」
如果非要使用遞歸的中序的方式寫，也可以，如下代碼就可以避免節點左右孩子翻轉兩次的情況：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left); // 左
swap(root->left, root->right); // 中
invertTree(root->left); // 注意 這裡依然要遍歷左孩子，因為中間節點已經翻轉了
return root;
}
};
代碼雖然可以，但這畢竟不是真正的遞歸中序遍歷了。
但使用迭代方式統一寫法的中序是可以的。
代碼如下：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
if (node->right) st.push(node->right); // 右
st.push(node); // 中
st.push(NULL);
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
swap(node->left, node->right); // 節點處理邏輯
}
}
return root;
}
};
為什麼這個中序就是可以的呢，因為這是用棧來遍歷，而不是靠指針來遍歷，避免了遞歸法中翻轉了兩次的情況，大家可以畫圖理解一下，這裡有點意思的。
總結「本周我們都是講解了二叉樹，從理論基礎到遍歷方式，從遞歸到迭代，從深度遍歷到廣度遍歷，最後再用了一個翻轉二叉樹的題目把我們之前講過的遍歷方式都串了起來。」
下周依然是二叉樹，大家加油！