樹的結構差不多告一個段落，再來就資料結構的順序上，會進入圖的單元，也就是樹結構的進階。
圖的結構裡有兩種主要遍歷模式，分別是深度優先搜尋(DFS)和廣度優先搜尋(BFS)，在樹的這幾篇裡面，其實我們已經用樹的概念帶過了簡單版的遍歷模式。
DFS 相關的是前中後序，BFS 相關的是層級遍歷。

在進入圖之前，想針對 DFS 再多講一個概念：回朔算法。
回朔算法指的是題目給予結構，我們須選用結構中的幾個節點並回傳選擇的項目，讓回傳的項目符合題目要求。
樹結構也會有這種題目，以二元樹為例，每一次往子節點的分歧，都是一種選擇，這邊要選擇左子樹、還是右子樹，還是在這邊終止。
回朔算法的題目大多會用遞迴處理，如我們練習前中後序遍歷一樣，先決定終止條件、對單一節點的處理，差異在往左右選擇時多了採用選擇的概念，還有視題目會有撤銷選擇的概念。

今天讓我們用這篇來看一下回朔的題目，以及他的結構跟之前的前中後序相似之處。

Path Sum

給定一棵樹和一個目標數，要求我們判斷有沒有任一條從根節點到葉節點，節點總和正好為目標數，有則回傳是，沒有回傳否。
寫成遞迴，函式的定義會是給根節點，給目標值，找有沒有從這個點到葉正好等於目標值的可能，有則回傳是。
可以想見，每當我們走到某個節點，表示我們採計了那個節點、選擇走了這個節點，也就是目標值可以被扣去該節點的值，然後再繼續往下走，問題就可以被簡化成重複步驟，減那個節點、如果減完正好等於零，節點本身也是葉節點，則題目要求的組合存在。
只要左右子樹發展下去，有任一合法組合存在，則回傳是(題目只問有沒有存在)。
照這樣的概念，我們的遞迴寫出來會是像這樣：

public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }   
        if(root.val == targetSum && root.left == null && root.right == null){
            return true;
        }        
        return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);
    }
}

這題是比較簡單的回朔，甚至還沒帶到回朔的概念，只帶到了選擇、累進的看法。
累進的對象就是路徑加總，只是我們用目標扣去當前節點這個行為作為選擇，剛好傳值的時候，不會影響其他呼叫，所以不用做撤銷(把節點值加回去)，讓這題變的比較單純。
下題讓我們看看類似的題目，就會帶到回朔中的撤銷怎麼加到題目裡。

Path Sum II

給定一個二元樹的根節點，以及一個目標值，回傳所有從根節點到葉子節點，節點值加總等於目標值的組合。

「所有組合」與「從根到葉子」就讓我們知道我們必須來遍歷整棵樹才能得到答案，我們可以先決定怎麼遍歷。
以這題而言，前中後序的遍歷方式其實都可以。
終止條件是當碰到的點為空，則結束處理。
我們新定義一個遍歷樹的函式，除了傳入樹結構、目標樹以外，還要多傳入一個已做選擇(list)。
每當我們遍歷到一個不為空的節點，把該節點的值加入已做選擇列表中，表示現在這個路徑裡是有這個點的。
回退的時候，把最後一個加入選擇列表的點移除，表示我們往後走了一步。
這些是大概邏輯，如果看懂了，可以嘗試寫寫看；不太清楚的話，我們先看程式碼怎麼處理。

public class Solution {
    public List<IList<int>> Result;
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        Result = new List<IList<int>>();
        Traverse(root, targetSum, new List<int>());
        return Result;
    }

    public void Traverse(TreeNode root, int sum, List<int> list){
        if(root == null){
            return;
        }
        list.Add(root.val);
        if(root.val == sum && root.left == null && root.right == null){
            Result.Add(new List<int>(list));
            list.RemoveAt(list.Count - 1);
            return;
        }
        Traverse(root.left, sum - root.val, list);
        Traverse(root.right, sum - root.val, list);
        list.RemoveAt(list.Count - 1);
        return;
    }
}

這題我的寫法是用前序遍歷，相較本來的前序遍歷，多的就是這個選擇列表，跟撤銷選擇。
最後把完成的選擇加入的時候，要注意語言類型，關於傳參考跟傳值，避免傳入參考，結果該參考在後續被修改。
像我這邊 C# 用 new List<int>(list) 來用 list 重新複製一個值一樣但斷開參考連結，避免後續我修改 list 的時候存在 Result 裡的元素也被修改。

這樣做選擇->確認選擇結果->符合條件加入解答->撤銷選擇的流程，我們會在回朔算法相關的題目中一再看到。
這兩個練習範例是回朔中最基本的概念且跟樹結構相關，更複雜一點的回朔，讓我們在進入圖的資料結構後再拉一篇來討論。