深度優先搜尋、遞歸和回溯，周遊法和分治法的定義和差別

遞歸 Recursion

遞歸函數：調用自己的函數。

遞歸算法：大問題依賴于小問題，先遞歸函數求解小問題

一般算法中的遞歸指的是遞歸函數。

深度優先搜尋 Depth First Search

遞歸函數實作，在搜尋過程中優先搜尋更深的點而不是同層的點的算法。

也可以用棧代替遞歸函數，不過一般是都遞歸實作DFS。

回溯 Backtracking

回溯法：就是深度優先搜尋算法

回溯操作：遞歸函數在回到上一層遞歸調用時，将參數該回到調用前的值，這個操作就是回溯。

周遊 VS 分治法

周遊：一個小人拿着一個記事本走遍所有節點

分治法：配置設定小弟去做子任務，自己對子任務的結果進行彙總

結果的儲存：

周遊：通常用一個全局變量或共享參數

分治法：通常利用傳回值記錄子問題的結果，目前任務對子任務的結果進行彙總。

二叉樹分治法模闆：

public 傳回結果類型 function(TreeNode root)
    {
        if(root==null){
            空樹傳回結果;
        }
        
        if(root.left==null && root.right==null)
        {
            葉子節點傳回的結果;
        }
        
        左子樹傳回結果=function(root.left);
        右子樹傳回結果=function(root.left);
        目前節點的結果=按照一定方法合并左右子樹的結果;
        return 目前節點的結果;
    }           

二叉樹的所有路徑——分治法、回溯法

題目：二叉樹的所有路徑

給你一個二叉樹的根節點 

root

 ，按 任意順序 ，傳回所有從根節點到葉子節點的路徑。

示例 1：

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]           

題解

/**
     * 回溯法
*/
    class Solution {
        List<String> res;
        public void dfs(TreeNode root, List<Integer> node)
        {
            if(root==null) return;
            node.add(root.val);
            if(root.left==null && root.right==null)
            {
                StringBuilder sb=new StringBuilder();
                for(int i=0;i<node.size();i++)
                {
                    if(i==0) sb.append(node.get(i));
                    else sb.append("->"+node.get(i));
                }
                res.add(sb.toString());
                node.remove(node.size()-1);
                return;
            }

            dfs(root.left, node);
            dfs(root.right, node);
            node.remove(node.size()-1);
        }
        public List<String> binaryTreePaths(TreeNode root) {
            res=new ArrayList<>();
            List<Integer> node=new ArrayList<>();
            dfs(root, node);

            return res;
        }
    }           

/**
     * 分治法
     * O(n2)
     */

    class Solution2 {
        public List<String> dfs(TreeNode root)
        {
            List<String> paths=new ArrayList<>();
            if(root==null) return paths;
            if(root.left==null && root.right==null)
            {
                paths.add(""+root.val);
                return paths;
            }

            for(String path: dfs(root.left))
                paths.add(root.val+"->"+path);
            for(String path: dfs(root.right))
                paths.add(root.val+"->"+path);
            return paths;
        }
        pu