写一个递归与回溯算法

写一个递归与回溯算法

在我们生活中的树就是一种递归的结构，或者说只要形成了树结构的都可以用递归的方式来处理遍历。主枝干会有很多的分支，每一个分支和主干一样也同样会有其他更多的子分支，每一个更小的分支还会有更多的子分支...

递归本质就是遍历整颗树的一种方式(一个不差的扫描树的每一个叶子获取所有的可能性都这也是递归存在的意义)，从主干开始遍历整颗树和从某一个分支遍历所在的子树本质是一样的，不过是一个更小的问题罢了。当更小的问题解决之后，会自动回到子问题开始的位置，当所有子分支都被解决之后，会回到主枝干一开始解决问题的起始地方，这时候整个问题都被解决了。

递归是由递归的终止条件与更小的子递归问题共同构成了原问题，是一种自顶向下解决问题的算法思维。

斐波那契数列

0 1 1  2 3 5 7 12 ...

如何写一个递归算法

写递归算法的时候，不用考虑调用子递归函数内部具体逻辑是怎么样实现的，想象自然界中的树结构，每一个子分支也是一颗树。调用递归函数会得到更小范围的答案，因为原问题和子问题有着相同的逻辑，所以整个问题都解决了。

比如上面的斐波那契数列，首先要找到规律(是否形成类似于树的递归结构逻辑)，不用想 fib(n-1)+fib(n-2)是怎么执行和计算的。调用 fib(n-1)+fib(n-2)会得到每一个子过程的答案，因为整个逻辑是一样的所以这也一定是最终的答案，所以不用想太多内部的参数与执行的过程，因为逻辑是一样一定会的得到逻辑想要的答案。而调用递归逻辑的时候只用考虑一个问题就是递归的终止条件，n-1与n-2不能一直的执行下去，所以总会有递归的终止条件，根据递归结构来写...

二叉树的前中后序遍历

带入根节点，如果节点不为空的话，前序遍历左孩子之后前序遍历右孩子，因为左孩子与右孩子同样是一颗二叉树

跳出代码是怎么样运行的，具体的语义很清楚就是做一件事情

写递归函数的时候，特别要求空也是一个特殊的二叉树

递归与栈的紧密关系

前序遍历新执行的preorder与原来的preorder没有任何的关系因为传入的参数完全不同，在子函数执行完毕之前原函数都是暂停，执行完毕后会自动退回到上一次暂停的位置继续执行直到整个函数执行完递归结束。

系统栈具体在递归的哪里起作用?

暂停去执行另外的函数这个过程就需要使用栈这种数据结构，往栈中推入的内容就是上一层具体执行到哪里的信息。递归会自动返回到上一层暂停的位置，就是取出栈顶的元素判断该执行哪一步。

遍历右孩子返回的时候，获取栈顶元素信息已经做完了函数里面的所有三件事情，整个子函数结束还要返回上一层还是取出栈顶的元素。

运用栈模拟递归

因为栈的先入后出递归的过程先推入右孩子然后推入左孩子，最后输出。

    public List inorderTraversal(TreeNode root) {

        ArrayList res = new ArrayList();
        if(root == null)
            return res;

        Stack stack = new Stack();
        stack.push(new Command("go", root));
        while(!stack.empty()){
            Command command = stack.pop();

            if(command.s.equals("print"))
                res.add(command.node.val);
            else{
                assert command.s.equals("go");
                if(command.node.right != null)
                    stack.push(new Command("go",command.node.right));
                if(command.node.left != null)
                    stack.push(new Command("go",command.node.left));
                stack.push(new Command("print", command.node));
            }
        }
        return res;
    }

栈的其他应用

给定一个字符串看括号是否匹配()[]{} 都是匹配的

如果是左括号的话放入栈中，如果是右括号的话取出栈中的元素判断是否匹配括号。

如果是右括号的话，如果此时栈中没有元素也是没有办法进行匹配，最后判断栈中所有的元素是否都已经匹配过。

    public boolean isValid(String s) {
        //Deque deque = new LinkedList(); //模拟栈
        Stack stack = new Stack();
        for( int i = 0 ; i < s.length() ; i ++ )
            if( s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')
                stack.push(s.charAt(i));
            else{

                if( stack.size() == 0 )
                    return false;

                Character c = stack.pop();

                Character match;
                if( s.charAt(i) == ')' )
                    match = '(';
                else if( s.charAt(i) == ']' )
                    match = '[';
                else{
                    assert s.charAt(i) == '}';
                    match = '{';
                }

                if(c != match)
                    return false;
            }

        if( stack.size() != 0 )
            return false;

        return true;
    }

底层源码集合中寻找某个值

递归实现二叉树的最高深度

首先考虑到的是计算深度到叶子节点就要结束递归并进行统计了，二叉树左右孩子都是同样的遍历逻辑，每次进行递归下一层的时候都会进行+1操作。

如何反转一颗二叉树

首先反转做子树，再反转右子树，然后对整棵树进行反转(左右子树交换位置)

如果传入的时候null，不能反转要进行非空判断

    public TreeNode invertTree(TreeNode root) {

        if(root == null)
            return null;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }

判断是否存在从根到叶子节点和为sum的路径

注意递归的终止条件，不能直接判断最后传入的root是否为0，求sum=5时候，因为5不是叶子节点。

node为空判断忽视了父节点是否为叶子节点，如果root为空的话直接访问做子树和右子树会报空指针错误，所以最开始要判空

    public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null)
            return false;

        if(root.left == null && root.right == null)
            return sum == root.val;

        return hasPathSum(root.left, sum - root.val)
                || hasPathSum(root.right, sum - root.val);
    }

返回二叉树从根节点到叶子节点的字符串

和现实中的树结构是一样的，整个过程是都是先进入一个枝杈，遍历完了之后回到一开始进入这个枝杈的地方继续遍历别的枝杈，二叉树遍历左子树以及遍历右子树，最后合并在一起。

和指针相关的问题一定要考虑空指针，最后左子树和右子树遍历的结果都会存到res中，返回即可。

    public List binaryTreePaths(TreeNode root) {

        ArrayList res = new ArrayList();

        if(root == null)
            return res;

        if(root.left == null && root.right == null){
            res.add(Integer.toString(root.val));
            return res;
        }

        List leftPaths = binaryTreePaths(root.left);
        for(String s: leftPaths){
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        List rightPaths = binaryTreePaths(root.right);
        for(String s: rightPaths) {
            StringBuilder sb = new StringBuilder(Integer.toString(root.val));
            sb.append("->");
            sb.append(s);
            res.add(sb.toString());
        }

        return res;
    }

判断路径上有多少条路径，路径上所有节点的和为sum

思维一定要清晰，先考虑与原先的问题有什么不同的地方，往往更加复杂的问题都是由简单基础的问题增加了一定的条件。这个问题也包含了上面从根节点到叶子节点的情况，也包括了不包括根节点到叶子节点的情况，一共这两种情况。

从根节点到叶子节点一样的逻辑，获取左右子树一共有多少个满足条件的记录，然后保存在一开始定义的变量中。如果不包括根节点那么直接从左子树和右子树开始走相同的逻辑。

    // 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
    public int pathSum(TreeNode root, int sum) {

        if(root == null)
            return 0;

        return findPath(root, sum)
                + pathSum(root.left , sum)
                + pathSum(root.right , sum);
    }

    // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
    // 返回这样的路径个数
    private int findPath(TreeNode node, int num){

        if(node == null)
            return 0;

        int res = 0;
        if(node.val == num)
            res += 1;

        res += findPath(node.left , num - node.val);
        res += findPath(node.right , num - node.val);

        return res;
    }

寻找两个节点的二分搜索树的公共祖先

首先要考虑蕴含的递归逻辑，如果p和q都小于node的话，那么最近公共祖先一定不是node，公共祖先在左子树中，同理都大于node在右子树中，如果一个小于node一个大于node那么公共祖先一定是node本身了。

往往会漏掉一种情况，如果p是node本身的话，那么p就是q的公共节点，所以写递归的算法的一开始的时候一定要考虑到所有的递归逻辑情况再去写，一般特殊的情况容易遗漏。

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(p == null || q == null)
            throw new IllegalArgumentException("p or q can not be null.");

        if(root == null)
            return null;

        if(p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        if(p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);

        assert p.val == root.val || q.val == root.val
                || (root.val - p.val) * (root.val - q.val) < 0;

        return root;
    }

给定电话按键如23，求所有按键对应的字母和 ，每一个数字对应多个字母如2对应abc、3对应def字符。

仔细发现这个问题也形成了递归树的结构，递归下去的条件是index+1，选a的话会有def三种情况对应，选b也会有三种情况对应，递归的边界就是到达了给定数字组合的长度递归结束。

    private String letterMap[] = {
                " ",    //0
                "",     //1
                "abc",  //2
                "def",  //3
                "ghi",  //4
                "jkl",  //5
                "mno",  //6
                "pqrs", //7
                "tuv",  //8
                "wxyz"  //9
    };

    private ArrayList res;

    public List letterCombinations(String digits) {

        res = new ArrayList();
        if(digits.equals(""))
            return res;

        findCombination(digits, 0, "");
        return res;
    }

    // s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
    // 寻找和digits[index]匹配的字母, 获得digits[0...index]翻译得到的解
    private void findCombination(String digits, int index, String s){

        System.out.println(index + " : " + s);
        if(index == digits.length()){
            res.add(s);
            System.out.println("get " + s + " , return");
            return;
        }

        Character c = digits.charAt(index);
        assert  c.compareTo('0') >= 0 &&
                c.compareTo('9') {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int m, n;
    private boolean[][] visited;

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

        if(board == null || word == null)
            throw new IllegalArgumentException("board or word can not be null!");

        m = board.length;
        if(m == 0)
            throw new IllegalArgumentException("board can not be empty.");
        n = board[0].length;
        if(n == 0)
            throw new IllegalArgumentException("board can not be empty.");

        visited = new boolean[m][n];
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++)
                if(searchWord(board, word, 0, i, j))
                    return true;

        return false;
    }

    private boolean inArea( int x , int y ){
        return x = 0 && x < m && y = 0 && y < n;
    }

    // 从board[startx][starty]开始, 寻找word[index...word.size())
    private boolean searchWord(char[][] board, String word, int index,
                               int startx, int starty){

        //assert(inArea(startx,starty));
        if(index == word.length() - 1)
            return board[startx][starty] == word.charAt(index);

        if(board[startx][starty] == word.charAt(index)){
            visited[startx][starty] = true;
            // 从startx, starty出发,向四个方向寻
            for(int i = 0 ; i < 4 ; i ++){
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if(inArea(newx, newy) && !visited[newx][newy] &&
                        searchWord(board, word, index + 1, newx, newy))
                    return true;
            }
            visited[startx][starty] = false;
        }
        return false;
    }{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    private boolean visited[][];

    public int numIslands(char[][] grid) {

        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;

        m = grid.length;
        n = grid[0].length;

        visited = new boolean[m][n];

        int res = 0;
        for(int i = 0 ; i < m ; i ++)
            for(int j = 0 ; j < n ; j ++)
                if(grid[i][j] == '1' && !visited[i][j]){
                    dfs(grid, i, j);
                    res ++;
                }

        return res;
    }

    // 从grid[x][y]的位置开始,进行floodfill
    // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
    private void dfs(char[][] grid, int x, int y){

        //assert(inArea(x,y));
        visited[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if(inArea(newx, newy) && !visited[newx][newy] && grid[newx][newy] == '1')
                dfs(grid, newx, newy);
        }

        return;
    }

    private boolean inArea(int x, int y){
        return x = 0 && x < m && y = 0 && y < n;
    }= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }

获取从s为起点的一条路径

定义一个form数组来表示某个节点是从从哪一个节点过来的，最后返回路径需要栈来倒推出从哪个点过来的，直到回到原点。因为原点没有从其他店过来所以保持初始化为-1。

import java.util.Vector;
import java.util.Stack;

public class Path {

    private Graph G;   // 图的引用
    private int s;     // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;         // 记录路径, from[i]表示查找的路径上i的上一个节点

    // 图的深度优先遍历
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public Path(Graph graph, int s){

        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;

        // 寻路算法
        dfs(s);
    }

    // 查询从s点到w点是否有路径
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    Vector path(int w){

        assert hasPath(w) ;

        Stack s = new Stack();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector res = new Vector();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert hasPath(w) ;

        Vector vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}