范疇：遞歸

1驹饺、青蛙跳臺(tái)階

青蛙跳臺(tái)階算法，每次可以跳1級(jí)或兩級(jí)鱼炒，請(qǐng)問(wèn)有n級(jí)臺(tái)階蝌借，有多少種算法俐巴，遞歸和非遞歸如何寫(xiě)

• 遞歸：

  public int JumpFloor(int n)
   {
     if (n < 0)
         return 0;
     int[] fibArry = { 0, 1, 2 };
     if (n < 3)
         return fibArry[n];
     return JumpFloor(n - 1) + JumpFloor(n - 2);
   }
  

• 非遞歸：

  public int JumpFloor(int n)
    {
        if (n < 0)
            return 0;
        int[] fibArry = { 0, 1,2 };
        if (n < 3)
            return fibArry[n];
        long nReturn = 0L;
        long fibFirst=1L;
        long fibTow=2L;
        for (int i = 3; i <= n; i++)
        {
            nReturn = fibFirst + fibTow;
            fibFirst=fibTow ;
            fibTow = nReturn;
        }
        return nReturn;
    }
  

2、變態(tài)跳臺(tái)階 來(lái)自抛嚎模客網(wǎng)

一只青蛙一次可以跳上1級(jí)臺(tái)階劣光，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法牲剃。

分析：
關(guān)于本題雄可，前提是n個(gè)臺(tái)階會(huì)有一次n階的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2階一次跳2階的次數(shù)聪舒。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

說(shuō)明：
1）這里的f(n) 代表的是n個(gè)臺(tái)階有一次1,2,...n階的 跳法數(shù)虐急。
2）n = 1時(shí)止吁，只有1種跳法，f(1) = 1
3 ) n = 2時(shí)盼理，會(huì)有兩個(gè)跳得方式俄删，一次1階或者2階，這回歸到了問(wèn)題（1） 举哟，f(2) = f(2-1) + f(2-2)
4 ) n = 3時(shí)迅矛，會(huì)有三種跳得方式，1階壶硅、2階、3階椒舵，
那么就是第一次跳出1階后面剩下：f(3-1);第一次跳出2階约谈，剩下f(3-2)；第一次3階泼橘，那么剩下f(3-3)
因此結(jié)論是f(3) = f(3-1)+f(3-2)+f(3-3)
5 ) n = n時(shí)迈勋，會(huì)有n種跳的方式，1階重归、2階...n階厦凤，得出結(jié)論：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

由以上已經(jīng)是一種結(jié)論泳唠，但是為了簡(jiǎn)單，我們可以繼續(xù)簡(jiǎn)化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：f(n) = 2f(n-1)

7 ) 最終結(jié)論 在n階臺(tái)階拓哺，一次有1脖母、2、...n階的跳的方式時(shí)烤礁，總得跳法為：

          | 1        ,(n=0 ) 
f(n) =    | 1        ,(n=1 )
          | 2*f(n-1) ,(n>=2)

代碼：

public class Solution {
public int JumpFloorII(int target) {
    
    if(target < 0){
        return -1;
    }else if(target == 0 || target == 1){
        return 1;
    }else{
        return 2*JumpFloorII(target-1);
    }
}
}

范疇：樹(shù)

題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果脚仔，請(qǐng)重建出該二叉樹(shù)舆绎。
假設(shè)輸入的 前序遍歷 和 中序遍歷 的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8} 和中序遍歷序列{4,7,2,1,5,3,8,6}猎醇，則重建二叉樹(shù)并返回。

/**
*Definition for binary tree
*struct TreeNode {
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

    int inlen = in.size();
    if(inlen == 0){
        return NULL;
    }
    vector<int> left_pre,right_pre,left_in,right_in;
    
    // 創(chuàng)建根節(jié)點(diǎn)阻问，根節(jié)點(diǎn)肯定是 前序遍歷 的第一個(gè)數(shù)
    TreeNode* head = new TreeNode(pre[0]);
    
    // 找到 中序遍歷 根節(jié)點(diǎn)所在位置称近，存在變量gen中
    int gen = 0;  // 從中序遍歷中找到的 根節(jié)點(diǎn)的坐標(biāo)
    for(int i = 0; i < inlen; i++){
        if(in[i] == pre[0]){
            gen = i;
            break;
        }
    }
    // 接下來(lái)兩個(gè)for循環(huán)判斷：哪些元素屬于該根節(jié)點(diǎn)的左邊曹鸠，哪些屬于右邊
    
    // 對(duì)于中序遍歷斥铺，根節(jié)點(diǎn)左邊的節(jié)點(diǎn)位于二叉樹(shù)的左邊晾蜘，根節(jié)點(diǎn)右邊節(jié)點(diǎn)位于二叉樹(shù)右邊
    // 利用這一點(diǎn)對(duì)二叉樹(shù)進(jìn)行歸并，先判斷左邊的
    for(int i = 0; i < gen; i++){
        left_in.push_back(in[i]);
        left_pre.push_back(pre[i+1]); //+1跳過(guò)前序的根節(jié)點(diǎn)
    }
    for(int i = gen+1; i < inlen; i++){
        right_in.push_back(in[i]);
        right_pre.push_back(pre[i]); //這里不用加1
    }
    // 和shell排序的思想類(lèi)似肆饶，取出前序和中序根節(jié)點(diǎn)左邊和右邊的子樹(shù)岖常，
    // 也就是前面兩個(gè)for循環(huán)中保存起來(lái)的前序和中序的左右子樹(shù)數(shù)組
    // 遞歸電泳該方法直到葉子節(jié)點(diǎn)
    head->left = reConstructBinaryTree(left_pre,left_in);
    head->right = reConstructBinaryTree(right_pre,right_in);
    
    return head;
}
};