递归，另一种形式的遍历

• 递归总结
• 一个小例子
• 题一 12. 矩阵中的路径
• 题二 剑指 Offer 34. 二叉树中和为某一值的路径

这里用自己的语言描述下，递归就是调用自己，在源代码还没有执行完毕时，开辟新的空间来进行计算，不断更新从开始到调用自己之间执行的代码；

我们可以总结出来：

1. 调用自己
2. 返回条件（即终止条件）

递归的常用实现：树的遍历，图的查询

递归看似麻烦，实际上雀氏不好理解
不断调用自己返回，就一定要明确好返回的条件，确定调用时可以正确返回；

class aaa {
    public static void main(String[] args) {
        aaa a  = new aaa();
        System.out.println(a.sum(3));
    }

    public int sum(int n) {
        if (n <= 1) {
            return 1;
        }
        return sum(n - 1) + n;
    }
}

这个题一看就知道是dfs，dfs最常见实现就是递归；

• 递归：调用自己，不断遍历，匹配所有char元素
• 返回条件：

1. 返回值类型是boolean类型；
2. 如果超过边界或者值对不上就直接返回false；
3. 如果走完就返回ture；
4. 在这里返回条件上去调用自己上下左右行走；

• 这里的判断条件其实就是一个剪枝的过程；

需要注意的是：

1. board[i][j] = '';指的是这里的元素已经被使用
2. 而这里的board[i][j] = word.charAt(len);指的是当返回递归的上一级时让元素恢复

class Solution {


    public boolean exist(char[][] board, String word) {

        // char[] arr = word.toCharArray();
        for(int i=0; i
            for(int j=0;j
                if(word.charAt(0)==board[i][j]){
                    if(dfs(board, word, i, j, 0)==true)return true;
                }
            }
        }
        return false;
    
    }

    boolean dfs(char[][] board, String word, int i, int j, int len){

        if(i>=board.length||i<0||j>=board[0].length||j<0||word.charAt(len)!=board[i][j])return false;
        if(word.length()-1 == len)return true;
        board[i][j] = '';
        boolean result = (dfs(board, word, i-1, j, len+1)||dfs(board, word, i+1, j, len+1)
                        ||dfs(board, word, i, j+1, len+1)||dfs(board, word, i, j-1, len+1));

        board[i][j] = word.charAt(len);
        return result;
    
    }
}

class Solution {
    public List> pathSum(TreeNode root, int sum) {
        LinkedList arr = new LinkedList<>();
        LinkedList> res = new LinkedList<>();
        dfs(root, sum, arr, res);
        return res;
        
    }
    void dfs(TreeNode root, int sum, LinkedList arr, LinkedList> res){

        if(root==null)return ;
        sum-=root.val;
        arr.add(root.val);
        if(sum==0 && root.right == null && root.left==null){
            res.add(new LinkedList(arr));
        }
        dfs(root.left, sum, arr, res);
        dfs(root.right, sum, arr, res);
        //这里的removeLast是LinkedList的方法，指的是每次递归完后，需要删除本节点的值，返回上一个根节点
        arr.removeLast();

    }

}