天天看点
返回

面试算法突击（三）递归的使用

有句话叫“迭代是人，递归是神”。

递归的使用大量应用在二叉树，链表等。

　　递归的难度就在于死脑筋，刚开始接触递归，往往会纠结于递归的每一个步骤，想方设法的弄明白递归的每一步是怎么走的，debug一步一步运行。这样做是有帮助的，但是当你接触大量的题目的时候，你会发现，其实抽象的概念我们可以用抽象的思维去理解。

　　你可以不以去了解每一步是怎么走的，你只需要弄明白俩件事：

1.整个递归的结束条件是什么？

2.递归的主体。

　　递归的结束条件往往是题设中很容易出现的条件。

比如说青蛙跳台阶，这是斐波那契数列的变种。

例1：题设结束条件

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

假如我要用递归来解决这道题，我首先来寻找递归结束条件。

　什么时候结束递归？

当n= =1或者n==2的时候，青蛙的跳法正好是n，全部结束，不需要再次递归了，答案已经出来了。

所以我的递归结束条件就是

if(n==1 || n==2)
             return n;

接下来，开始完成递归的主体，循环的调用自身。

加入青蛙第一次跳了一步，那么就应该返回fun（n-1）

加入青蛙第一次跳了俩步，那么就应该返回fun（n-2）

所以递归的主体就应该是

return JumpFloor(n-1)+JumpFloor(n-2);

完整代码：

public class Solution {
    public int JumpFloor(int target) {
        if(target= =1 || target==2)
             return target;
             return JumpFloor(target-1)+JumpFloor(target-2);

    }
}

所以，找到正确的递归结束条件是十分重要的。

例2：算数结束条件

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

 考虑到这个问题，想一想，如果我们每次把exponent>>1的值求出来再乘以自身，不断递归就可以结束了！

 我们的第一步依旧是如何找到递归的结束条件。

a^x，显而易见，当x==0的时候，值为1.

所以当我们只考虑a>0的时候，递归结束条件可以这么写

if(exponent==0) return 1;

是不是特别简单？

主方法体该怎么去解决？

  既然要计算指数为exponent>>1的值，那么我们干脆就先算出来，再考虑奇数还是偶数的问题。（如果是偶数可以不用考虑，除2正好除开）。

double half=prePower(base,exponent>>1);

先把奇数搞定。

if((exponent&1)==1)
            return base*half*half;

如果是偶数就直接返回。

完整代码：

public class Solution {
    public double Power(double base, int exponent) {
        if(exponent<0)//考虑指数小于0的情况
            return 1/prePower(base,-exponent);
        return prePower(base,exponent);
        
  }
    public double prePower(double base,int exponent){
        if(exponent==0) return 1;
        double half=prePower(base,exponent>>1);
        if((exponent&1)==1)
            return base*half*half;
        return half*half;
    }
}

例三：节点null结束条件

先讲讲链表。

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

输入: 1->1->2

输出: 1->2

public ListNode deleteDuplicates(ListNode head)

  链表在递归中的结束条件是最明朗的，也是最容易找的不过要注意点，你能找到的条件都写上。

比如，head= =null算一个，还有吗？

有，head.next==null也算，它们的返回值都可以是head.

所以结束条件为：

if(head==null || head.next==null){
            return head;
        }

然后再写递归主体。

if(head.val==head.next.val)
            return deleteDuplicates(head.next);
        else{
            head.next=deleteDuplicates(head.next);
            return head;
      }

  这里具体的逻辑是明显的，判断下一个节点是否与head相等。来做判断。

  if(head.val==head.next.val)为什么要 return deleteDuplicates(head.next)？

真正的关键是 head.next=deleteDuplicates(head.next);用来做节点连接，每次return抛出的节点都是来到这步来完成链表的重构。最后返回head。

  现在你可以用链表翻转来完成递归练习。或许你会使用迭代，Stack等方法，但是使用递归，如果你稍有不注意就会出现环的情况。

Node reverseLinkedList(Node node)

依旧是我们熟悉的结束条件：

if (node == null || node.next == null) {
return node;

我们需要返回的是什么？

是新链表的头结点，所以我们可以直接

Node headNode = reverseLinkedList(node.next);

获取新的头结点，我们需要重构链表！！这是尤为重要的工作。使用next将节点们重新连起来。

node.next.next = node;

  我习惯用“下一个”来描述next，这样我们可以翻译下：node的下一个的下一个是node。emmm，看起来怪怪的，但是，当你把node.next看成一个整体，node.next的下一个是node，看起来就好多了。

  看起来似乎只需要return headNode就可以完成工作了。但是！！有个重要的问题，node1=node.next，node1的下一个是node，没问题，刚刚写的，node的下一个是什么？node.next=node1。node的下一个是node1.好像哪里出了问题？这是单向链表啊！！

出现环了，所以我们要赶紧加上node.next = null，意味着解构，解开原先的链表关联。

完整代码：

public Node reverseLinkedList(Node node) {
if (node == null || node.next == null) {
return node;
} else {
Node headNode = reverseLinkedList(node.next);
node.next.next = node;
node.next = null;
return headNode;
}
}

  树的问题绝大部分意味着递归，因为它特殊的结构导致，往往使用递归会比迭代更容易有思路，前提是你别想太多。怎么简单怎么来。

先整个最简单的，翻转下二叉树吧。它有个专业的名词叫做“二叉树的镜像”。

public void Mirror(TreeNode root)

  话不多说，我先干为敬。二叉树的递归无非就是“自上而下，由左至右”。

先找结束条件，if(root==null) return ;没有返回值，只是结束方法。

然后干嘛？

该干嘛干嘛，翻转呗，类似于swap（）函数，左节点，右节点互换。

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

  完了自上而下，我不需要考虑子树们怎么递归，反正递归的过程都一样，递归的结束我也写出来了，无非就是先左子树，再右子树。左子树的根，右子树的根都是显而易见的。

完整代码：

public void Mirror(TreeNode root) {
        if(root==null) return ;
        TreeNode left=root.left;
        root.left=root.right;
        root.right=left;
        Mirror(root.left);
        Mirror(root.right);
        
    }

树的问题往往都在左右节点的判断上，

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

简单翻译下，就是看看A中是否包含B.

什么时候包含？什么时候开始判断？判断的时候结束标志是什么？

什么时候包含，A中的子树和B树一模一样；

什么时候判断？当A树中有一个节点nodeA和B树的root相同就开始做下一步判断，拿nodeA的子节点和B 的rootB的子节点比较；

什么时候结束的标志，只要有一个节点不一样就返回false，拿A中其他的节点和rootB重新比较，直到所有的节点都相同，执行到rootB==null的时候，在这期间没有返回false结束，那么就算是OK了,返回true。

private boolean pre(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val!=root2.val) return false;
        if(root1.val==root2.val){
            return pre(root1.left,root2.left)&& pre(root1.right,root2.right);
        }
        return false;
    }

  这里有个细节需要注意：为什么要把 if(root2= =null) return true;放在最前面。

因为不管root1是否为空，只要root2= =null，我都认为B是A的子树。如果

if(root1= =null) return false;放在最前面就会丢失正确的返回条件—root1= =null && root2==null 也应该返回true。注意执行的流程。

完整代码：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
         boolean flag=false;
        if(root1!=null && root2!=null){
               if(root1.val==root2.val){
                  flag=pre(root1,root2);
                 
            }
            if(flag==false){
                return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
            }
 
        }
        return flag;
    }
    private boolean pre(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val!=root2.val) return false;
        if(root1.val==root2.val){
            return pre(root1.left,root2.left)&& pre(root1.right,root2.right);
        }
        return false;
    }
}

递归就像是走迷宫，万一走到头发现走不出去，或者走到底，你就要考虑退回去重新走另外一条路。

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

这里寻找递归结束条件就不再赘述了，先贴代码

public class Solution {
    ArrayList<ArrayList<Integer>> listAll=new ArrayList<>();
    ArrayList<Integer> list=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null)
            return listAll;//递归的结束标志在这里。
        list.add(root.val);
        target-=root.val;
        if(target==0&&root.left==null&&root.right==null){
            //添加节点的步骤在这里
            listAll.add(new ArrayList<>(list));
        }
        if(target>0 && root.left!=null){
            FindPath(root.left,target);
        }
        if(target>0 &&root.right!=null){
           FindPath(root.right,target);
        }
        list.remove(list.size()-1);//回退的步骤在这里！
        return listAll;
    }
}

如果没有回退的步骤，会发现递归到叶子节点如果还没有找到路径，就不会返回父节点继续寻找！

如果你理解了这道题，你可以去自己完成打印二叉树所有路径的题目，返回一个list，包含了所有的路径。（从头结点到任意叶子节点）

与这相似的题型还有全排列，全排列的关键步骤是在交换俩个数之后再次交换回来！

ArrayList<String> Permutation(String str) {
    ArrayList<String> re = new ArrayList<String>();
    if (str == null || str.length() == 0) {
             return re;
}
HashSet<String> set = new HashSet<String>();
   fun(set, str.toCharArray(), 0);
   re.addAll(set);
   Collections.sort(re);
          return re;
}
//建议粘贴到Idea Debug运行。
void fun(HashSet<String> re, char[] str, int k) {
      if (k == str.length) {
           re.add(new String(str));
           return;
        }
           for (int i = k; i < str.length; i++) {
               swap(str, i, k);
               fun(re, str, k + 1);
               swap(str, i, k);
       }
}
void swap(char[] str, int i, int j) {
      if (i != j) {
       char t = str[i];
       str[i] = str[j];
       str[j] = t;
}
}
面试算法突击（三）递归的使用

总结下，递归在大量练习下会有很好的效果，往往你需要的只是灵光一闪的思路。类似于中国象棋要考虑多手，递归一般只考虑结束，现在和下一步。下下步就不要多操心了。

面试算法题
上一篇: 面试算法突击（一）堆排序
下一篇: LinkedList集合（JDK1.8）

继续阅读