開辟新專題！不擅長的圖它來了來了！（莫名激動

進度：10/100

另：沒想到給自己挖了個坑，可以用dfs的基本上也可以用bfs，看來要雙線并行了。

補：圖算法是我近期得有30%的焦慮來源了，但是不管三七二十一，奧力給，干他兄弟們！

兩周的提交記錄。努力努力再努力！

?

原題1：

給你二叉樹的根節點?root?，返回它節點值的?前序?遍歷。

原題2：

給定一個二叉樹的根節點?root?，返回?它的?中序?遍歷?。

原題3：

給你一棵二叉樹的根節點?root?，返回其節點值的?后序遍歷?。

原題4：

給你二叉樹的根節點?root?，返回其節點值的?層序遍歷?。 （即逐層地，從左到右訪問所有節點）。

原題5：

給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。

原題6：

給你二叉樹的根節點?root?和一個表示目標和的整數?targetSum?。判斷該樹中是否存在?根節點到葉子節點?的路徑，這條路徑上所有節點值相加等于目標和?targetSum?。如果存在，返回?true?；否則，返回?false?。

葉子節點?是指沒有子節點的節點。

原題7：

給你二叉樹的根節點?root?和一個整數目標和?targetSum?，找出所有?從根節點到葉子節點?路徑總和等于給定目標和的路徑。

葉子節點?是指沒有子節點的節點。

原題8：

給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明：葉子節點是指沒有子節點的節點。

原題9：

給定一個二叉樹，判斷它是否是?平衡二叉樹

? （平衡二叉樹?是指該樹所有節點的左右子樹的高度相差不超過 1。）

?

?

1.二叉樹的前序遍歷--簡單

中左右。

（1.遞歸。

（2。迭代。當棧不為空或節點不為空時，我們將root->val加入vector，一直入棧root的左節點直至root為空，說明左節點已經遍歷完，root指向棧頂的右節點，繼續循環。

（3.Morris迭代。還不會

?

2.二叉樹的中序遍歷--簡單

左中右。

棧的用法：

stk.top()，stk.pop()，stk.push()

思路：

（1.遞歸。先遍歷左節點，再將根節點入vector，再遍歷右節點。

（2.迭代。so，迭代與遞歸到底有什么區別，我一直認為他倆一樣。

區別：迭代是通過調用一個迭代器解決問題，譬如用一個for循環來計算1~100的和。遞歸是通過反復調用自身來解決問題。

我們使用一個棧，在它不為空或者節點不為空時，一直循環將當前指針指向左直至當前為空，然后將棧首出隊（此時當前節點已經沒有左節點，所以按中序遍歷原理，該根節點可以入vector了），入vector，當前節點再指向右（該節點左中都入vector了，該將右節點入vector了），然后循環。

（3.Morris迭代。

?

3.二叉樹的后序遍歷--簡單

左右中。

（1.遞歸。

（2.迭代。咱們就是說，一整個茅塞頓開，恍然大悟啊。后序遍歷是左右中，利用棧先入后出的特性，我們按中右左給節點壓進去，最后反轉一下vector就行了，

（3.Morris迭代。還不會

?

4.二叉樹的層序遍歷--簡單

（1.遞歸。忘記depth這個可利用的數據了。

（2.迭代。一層一層入總vector，即：每次隊列只會含有這一層的節點。注意，root!=nullptr是什么鬼循環判斷條件啊。

?

?

5.對稱二叉樹--簡單

隊列用法：

q.front()，q.pop()，q.push()

思路：

（1.遞歸。不簡述了，同上思路。要是世界的原理像遞歸一樣簡單就好了。

（2.迭代。簡直了，遞歸就像dfs的代名詞，迭代就是bfs的代名詞（阿雞瞎說，別打我）

用隊列來存，先入隊兩個頭節點，然后每次取出隊列頭部兩個節點進行比較，false的就考慮false的情況，暫時沒出錯的就將root1->left，root2->right，root1->right，root2->left入隊。

?

?

6.路徑總和--簡單

思路：

（1.遞歸。

（2.迭代。我發現dfs和bfs相對于別的算法沒有那么多細節，基本上邏輯對了代碼就對。

用兩個隊列分別存當前訪問的節點和當前節點的路徑總和。如果是葉子節點，檢查總和是否等于目標總和。將該節點存在的子節點與其路徑和入隊，循環進行至隊列為空（所有節點都遍歷完）為止。

?

?

7.路經總和 II--中等

（1.遞歸。有意思的是回溯的話，vector也會跟著回溯，不需要刪除上一輪加進去的元素。

?

8.二叉樹的最小深度--簡單

單純就想把這個題作為風向標放這，證明我兩種解法的碼都是自己敲出來的，吾已小成！喔哈哈哈哈

?

9.平衡二叉樹：
思路：

（1.自上而下遞歸。

（2.自下而上遞歸。有意思的是left和right都先等于其左右節點的子樹的值，然后看是否高度相差大于1或者子樹中有高度為-1，有則返回-1；沒有則返回高子樹+1。

?

彩蛋：

官方題解的優雅代碼：

return max(maxDepth(root->left), maxDepth(root->right)) + 1;

?

?