摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時(shí)間刪除鏈表結(jié)點(diǎn)。

本文的題目均來自于劍指offer中的題目，題目序號(hào)保持了書中的題目序號(hào)，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會(huì)出現(xiàn)題目序號(hào)的中斷。

面試題6：重建二叉樹
題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果都不含重復(fù)的數(shù)字。前序遍歷序列為{1,2,4,7,3,5,6,8}，中序遍歷序列{4,7,2,1,5,3,8，6}。
分析：根據(jù)前序遍歷和中序遍歷的定義可知，前序遍歷中的第一個(gè)值就是根節(jié)點(diǎn)的值，而在中序遍歷中根節(jié)點(diǎn)的值是在左子樹的后面右子樹的前面，由于樹中沒有重復(fù)的值所以可以通過對(duì)中序遍歷進(jìn)行一遍搜索來找到這個(gè)值，從而也可以確定這棵樹的左右子樹。確定了左右子樹后遞歸處理。
代碼實(shí)現(xiàn)

function node(data, left, right){  //用來表示一棵樹中的節(jié)點(diǎn)
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
function show(){
  return this.data;
} 

function rebuildBT(pre, mid){ //根據(jù)前序遍歷和中序遍歷重建這棵樹并且輸出頭節(jié)點(diǎn)
  var root; //保存頭結(jié)點(diǎn)
  var len = pre.length;
  if(len > 1){
    var data = pre[0]; //前序遍歷的第一個(gè)元素即樹的根節(jié)點(diǎn)
    for(var i = 0; i
面試題7：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目：用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù)appendTail和deleteHead，分別完成在隊(duì)列尾部插入節(jié)點(diǎn)和在隊(duì)列頭部刪除節(jié)點(diǎn)的功能。
分析：由于棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，且只能在棧頂來刪除數(shù)據(jù)，所以本題目的實(shí)現(xiàn)思路是先將隊(duì)列從頭到尾壓入棧中保存，如果要從尾部添加一個(gè)元素那么直接從棧頂壓入一個(gè)元素即可，如果是要從頭部刪除一個(gè)元素那么將隊(duì)列從棧1彈出保存到棧2，對(duì)棧2棧頂彈出一個(gè)元素再壓回棧1.
面試題目8：旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，稱之為一個(gè)數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如旋轉(zhuǎn)數(shù)組{3,4,5,1,2}的最小值為1.
分析：直觀的方法是對(duì)整個(gè)數(shù)組進(jìn)行一次遍歷，找出最小值。但是這種復(fù)雜對(duì)為o（n）的方法顯然不是最佳，因?yàn)槲覀冞@里沒有用到旋轉(zhuǎn)數(shù)組包含兩個(gè)已排序的子序列的特點(diǎn)。對(duì)于已排序的數(shù)組我們可以用二分法來進(jìn)行查找，可以將時(shí)間復(fù)雜度降低為（logn），那么這里我們也可以用相似的思路來實(shí)現(xiàn)。
代碼實(shí)現(xiàn)：
function minNum(inputArr){
  //輸入為旋轉(zhuǎn)數(shù)組，利用二分法來查找最小元素
  var len = inputArr.length;
  var first=inputArr[0], last=inputArr[len-1], location, min;
  if(len > 2){
    location = Math.ceil(len/2)-1;
    var value = inputArr[location];
    if(value >last){//說明這個(gè)中間元素在前面的數(shù)組中,那么最小的元素它之后
      min = minNum(inputArr.slice(location));
    }else if(value <= last){//說明這個(gè)中間元素在后面的數(shù)組中，最小元素在它之前
      min = minNum(inputArr.slice(0,location+1));
    }
  }else if(len === 2){
    min = inputArr[0]>inputArr[1] ? inputArr[1] : inputArr[0];
  }else{
    min = inputArr[0];
  }
  return min;
}
面試題9：斐波那契數(shù)列
前言：如果需要多次計(jì)算相同的問題通?？梢赃x擇用遞歸或者循環(huán)來實(shí)現(xiàn)，遞歸是在一個(gè)函數(shù)內(nèi)部調(diào)用自身，馴海則是通過設(shè)置計(jì)算值的初始值和終止條件在一個(gè)范圍內(nèi)重復(fù)計(jì)算。通常遞歸方法的代碼會(huì)比較簡潔，但是它也會(huì)有顯著的缺點(diǎn)，由于每次遞歸都是一次函數(shù)的調(diào)用，所以遞歸效率較低；同時(shí)遞歸中有很多運(yùn)算是重復(fù)的（分解的小問題存在重疊的部分），這會(huì)對(duì)性能造成影響；最重要的是遞歸還有可能造成調(diào)用棧的溢出。那么這個(gè)時(shí)候我們就可以適當(dāng)?shù)乜紤]一下用循環(huán)的方法來解決。
題目一：寫一個(gè)函數(shù)，輸入n求斐波那契數(shù)列的第n項(xiàng)。首先得知道斐波那契數(shù)列的第n項(xiàng)是如何定義的。定義其實(shí)就是如下面方法1函數(shù)描述。很明顯使用了遞歸，當(dāng)n很大的時(shí)候運(yùn)行效率低下不說還會(huì)造成調(diào)用棧溢出，那么我么用一種循環(huán)的方法來實(shí)現(xiàn)一下，如方法2。
//方法1
function fn(n){
 if(n <= 0){
     return 0;
 }else if(n == 1){
     return 1
 }else{
     return fn(n-1)+fn(n-2);
 }
}

//方法2
function fn(n){
  var result, r1, r2;
  if(n<=0){
    return 0;
  }else if(n == 1){
    return 1;
  }else{
    r1 = 1;
    r2 = 0;
    for(var i = 2; i<=n; i++){
      result = r1 + r2;
      r2 = r1;
      r1 = result;
      
    }
  }
  return result;
}

 

面試題13：在O（1）時(shí)間刪除鏈表結(jié)點(diǎn)。
題目：給定單向鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，定義一個(gè)函數(shù)在O(1)時(shí)間刪除該節(jié)點(diǎn)。
分析：在單鏈表中刪除一個(gè)結(jié)點(diǎn)，直觀的思路就是從鏈表頭節(jié)點(diǎn)開始，順序遍歷查找要?jiǎng)h除的節(jié)點(diǎn)，并在鏈表中刪除該節(jié)點(diǎn)。但是這樣的話時(shí)間復(fù)雜度就為o(n)。所以我們要換一種方法來做，刪除一個(gè)結(jié)點(diǎn)是不是必須要已知這個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)呢？答案是否定的。由于這里已知了刪除節(jié)點(diǎn)的指針，那么我們可以方便地得到下一個(gè)節(jié)點(diǎn)，我們把下一個(gè)節(jié)點(diǎn)的內(nèi)容復(fù)制到需要?jiǎng)h除的節(jié)點(diǎn)上覆蓋原有的內(nèi)容，再把下一個(gè)節(jié)點(diǎn)刪除，這就相當(dāng)于把當(dāng)前需要?jiǎng)h除的節(jié)點(diǎn)刪除掉了。