java數據結構與算法刷題目錄（劍指Offer、LeetCode、ACM）-----主目錄-----持續更新(進不去說明我沒寫完)：https://blog.csdn.net/grd_java/article/details/123063846

1. 深度優先

解題思路：時間復雜度O($n^2$),空間復雜度O(n)

1. 從最下層結點開始，以每個結點為根結點，再次從上到下深度優先遍歷
2. 試圖找到符合條件的路徑
3. 很顯然，是雙重深度優先遍歷
4. 先深度優先遍歷所有結點，然后每個結點還得再深度優先遍歷一下找路徑
5. 所以是N^2時間復雜度

代碼

class Solution {//計算路徑和public int pathSum(TreeNode root, int targetSum) {if (root == null) {return 0;}//獲取以當前為根結點的路徑和int ret = rootSum(root, targetSum);//深度優先遍歷ret += pathSum(root.left, targetSum);ret += pathSum(root.right, targetSum);return ret;}//計算當前根結點的路徑和，對于每個結點都進行從上到下的深度優先遍歷//看看有沒有符合條件的路徑-------窮舉法public int rootSum(TreeNode root, long targetSum) {int ret = 0;//深度優先，記錄符合條件的路徑數目if (root == null) {return 0;}int val = root.val;//獲取當前結點值if (val == targetSum) {//如果當前值 == targetSum 結果+1，注意這里targetSum是減去前面結點，還需要多少ret++;} //深度優先，傳入，targetSum - 當前結點值，還需要多少ret += rootSum(root.left, targetSum - val);//左子樹符合條件的ret += rootSum(root.right, targetSum - val);//右子樹符合條件的return ret;//返回當前結點符合條件的}
}

2. 前綴和

解題思路：時間復雜度O(n),空間復雜度O(n).其中空間復雜度是2n，因為需要一個map，深度優先遍歷需要棧空間也是n，所以是2n時間復雜度，比上一個方法的空間復雜度多一倍。但是時間復雜度比它快n倍

1. 深度優先遍歷
2. 遍歷過程中，記錄前綴和（就是從根結點到當前結點的和）到map中
3. 每遍歷一個結點，都用當前前綴和 - 目標值，看看差多少，并從map中找這個差值

1. 如果找到這個差值，說明當前前綴 - 當前路徑上的某個子前綴，是一個符合條件的路徑
2. 如果沒有，說明沒找到，繼續向下遍歷

4. 當某個結點深度遍歷完成，向上返回時，那么包含這個結點的前綴和就沒有用了，需要從map中去掉

圖解：找目標路徑長度為8

1. 初始狀態下，前綴map，key保存前綴0，value保存此前綴有幾個，為1
   
2. 深度遍歷根結點10，則當前路徑前綴長度為10，10 - 8 = 2，也就是當前前綴比目標值多2.不符合條件。繼續深度優先遍歷，并將當前前綴和10放入map，此前綴有目前有1個
   
3. 深度遍歷到結點5，當前路徑前綴和為15,15-8 = 7，map中找7找不到，所以將15:1放入map
   
4. 繼續遍歷到結點3，當前路徑前綴和為18,18 - 8 = 10.此時map中發現10，也就是說，當前路徑比目標值8多10，而10就在此路徑的子前綴中，所以我們可以去掉10這個結點，這樣我們就找到了第一個符合條件的路徑，5和3。另外不要忘了將當前前綴和放入map，也就是18:1放入map
   
5. 繼續向下，遍歷結點3，此時發現前綴和為21,21 - 8 = 13，map中沒有，放入前綴和21:1
   
6. 繼續向下，我們發現已經到底，需要回溯了，回到父結點之前，需要先刪除當前前綴和，21:1，然后再回父結點。之后繼續遍歷，重復上述步驟。
   

代碼: 官方增加了測試用例，所以相同的代碼已經無法擊敗100%了

class Solution {public int pathSum(TreeNode root, int targetSum) {Map<Long, Integer> prefix = new HashMap<Long, Integer>();//用Map保存前綴和prefix.put(0L, 1);//初始放入前綴和0，和其1return dfs(root, prefix, 0, targetSum);//進入遞歸}public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {if (root == null) return 0;int ret = 0;//符合條件的路徑條數curr += root.val;//當前路徑值（前綴和）//看看當前路徑和 - 目標值，是否等于路徑上的一個前綴//如果是的話，說明當前路徑，去掉某些前綴結點，剛好符合targetSum//如果沒有，那么ret依然是0ret = prefix.getOrDefault(curr - targetSum, 0);//將當前路徑前綴和，加入到map中prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);//深度優先ret += dfs(root.left, prefix, curr, targetSum);ret += dfs(root.right, prefix, curr, targetSum);//----------當此結點的遍歷出棧時，要將map中對應的前綴和去掉。否則其它路徑的前綴和很可能和當前路徑的前綴和沖突-------------prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);//返回符合條件路徑條數return ret;}
}