天天看點
傳回

面試算法突擊（三）遞歸的使用

有句話叫“疊代是人，遞歸是神”。

遞歸的使用大量應用在二叉樹，連結清單等。

　　遞歸的難度就在于死腦筋，剛開始接觸遞歸，往往會糾結于遞歸的每一個步驟，想方設法的弄明白遞歸的每一步是怎麼走的，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）

繼續閱讀