513.找樹左下角的值
題目鏈接：https://leetcode.cn/problems/find-bottom-left-tree-value/
解答：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
1.層序遍歷?
最簡(jiǎn)便的解法
2. 遞歸
題目要求：在樹的最后一行找到最左邊的值
如何確定是在最后一行？深度最大的葉子節(jié)點(diǎn)一定是最后一行
那么如何找最左邊的呢？可以使用前序遍歷（當(dāng)然中序，后序都可以，因?yàn)楸绢}沒有 中間節(jié)點(diǎn)的處理邏輯，只要左優(yōu)先就行），保證優(yōu)先左邊搜索，然后記錄深度最大的葉子節(jié)點(diǎn)，此時(shí)就是樹的最后一行最左邊的值。
（1）確定遞歸函數(shù)的參數(shù)和返回值
參數(shù)必須有要遍歷的樹的根節(jié)點(diǎn)，還有就是一個(gè)int型的變量用來記錄最長(zhǎng)深度，隨著遞歸的深入逐漸增加；需要類里的兩個(gè)全局變量，maxLen用來記錄最大深度，result記錄最大深度最左節(jié)點(diǎn)的數(shù)值，不需要返回值，所以遞歸函數(shù)的返回類型為void。
（2）確定終止條件
當(dāng)遇到葉子節(jié)點(diǎn)的時(shí)候，就需要統(tǒng)計(jì)一下最大的深度了，所以需要遇到葉子節(jié)點(diǎn)來更新最大深度。
（3）確定單層遞歸的邏輯
在找最大深度的時(shí)候，遞歸的過程中依然要使用回溯
112.?路徑總和??
題目鏈接：https://leetcode.cn/problems/path-sum/
解答：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
1. 遞歸
（1）確定遞歸函數(shù)的參數(shù)和返回類型
參數(shù)：需要二叉樹的根節(jié)點(diǎn)，還需要一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器用來計(jì)算二叉樹的一條邊之和是否正好是目標(biāo)和，計(jì)數(shù)器為int型。
再來看返回值，遞歸函數(shù)什么時(shí)候需要返回值？什么時(shí)候不需要返回值？這里總結(jié)如下三點(diǎn)：
如果需要搜索整棵二叉樹且不用處理遞歸返回值，遞歸函數(shù)就不要返回值。（這種情況就是本文下半部分介紹的113.路徑總和ii）
如果需要搜索整棵二叉樹且需要處理遞歸返回值，遞歸函數(shù)就需要返回值。 （這種情況我們?cè)?a target="_blank">236. 二叉樹的最近公共祖先?(opens new window)中介紹）
如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因?yàn)橛龅椒蠗l件的路徑了就要及時(shí)返回。（本題的情況）
（2）確定終止條件
首先計(jì)數(shù)器如何統(tǒng)計(jì)這一條路徑的和呢？
不要去累加然后判斷是否等于目標(biāo)和，那么代碼比較麻煩，可以用遞減，讓計(jì)數(shù)器count初始為目標(biāo)和，然后每次減去遍歷路徑節(jié)點(diǎn)上的數(shù)值。
如果最后count == 0，同時(shí)到了葉子節(jié)點(diǎn)的話，說明找到了目標(biāo)和。
如果遍歷到了葉子節(jié)點(diǎn)，count不為0，就是沒找到。
（3）確定單層遞歸的邏輯
因?yàn)榻K止條件是判斷葉子節(jié)點(diǎn)，所以遞歸的過程中就不要讓空節(jié)點(diǎn)進(jìn)入遞歸了。
遞歸函數(shù)是有返回值的，如果遞歸函數(shù)返回true，說明找到了合適的路徑，應(yīng)該立刻返回。
以上代碼中是包含著回溯的，沒有回溯，如何后撤重新找另一條路徑呢。
回溯隱藏在traversal(cur->left, count - cur->left->val)這里， 因?yàn)榘裞ount - cur->left->val?直接作為參數(shù)傳進(jìn)去，函數(shù)結(jié)束，count的數(shù)值沒有改變。
2.迭代
113.路徑總和ii
參數(shù)：需要二叉樹的根節(jié)點(diǎn)，還需要一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器用來計(jì)算二叉樹的一條邊之和是否正好是目標(biāo)和，計(jì)數(shù)器為int型。
1.遞歸
路徑總和ii要遍歷整個(gè)樹，找到所有路徑，所以遞歸函數(shù)不要返回值！
回溯：
count =count-node.left.val; 對(duì)應(yīng)count =count+node.left.val;
path.add(node.left); 對(duì)應(yīng) path.remove(path.size()-1);
2. 迭代的方法記錄路徑比較麻煩，沒有必要
106.從中序與后序遍歷序列構(gòu)造二叉樹?
來看一下一共分幾步：
第一步：如果數(shù)組大小為零的話，說明是空節(jié)點(diǎn)了。
第二步：如果不為空，那么取后序數(shù)組最后一個(gè)元素作為節(jié)點(diǎn)元素。如果該節(jié)點(diǎn)元素就是葉子節(jié)點(diǎn)，則直接返回該節(jié)點(diǎn)
第三步：找到后序數(shù)組最后一個(gè)元素在中序數(shù)組的位置，作為切割點(diǎn)
第四步：切割中序數(shù)組，切成中序左數(shù)組和中序右數(shù)組 （順序別搞反了，一定是先切中序數(shù)組）
第五步：切割后序數(shù)組，切成后序左數(shù)組和后序右數(shù)組
首先要切割中序數(shù)組，為什么先切割中序數(shù)組呢？
切割點(diǎn)在后序數(shù)組的最后一個(gè)元素，就是用這個(gè)元素來切割中序數(shù)組的，所以必要先切割中序數(shù)組。
第六步：遞歸處理左區(qū)間和右區(qū)間
105.從前序與中序遍歷序列構(gòu)造二叉樹
邏輯和106.?從中序與后序遍歷序列構(gòu)造二叉樹一樣
