【面試必備】手撕程式碼，你怕不怕？

• 2019 年 10 月 5 日
• 筆記

本文公眾號來源：我沒有三顆心臟作者：我沒有三顆心臟

前言：不管是遠程的影片面試，還是現場的面試，都有可能會有手撕程式碼的環節，這也是很多童鞋包括我(雖然還沒遇到過..)都很頭疼的東西，可能是因為 IDE 自動提示功能用慣了或是其他一些原因，總之讓我手寫程式碼就是感覺很奇怪..但是我想的話，這應該側重考察的是一些細節或者是習慣方面的一些東西，所以還是防患於未然吧，把一些可能手撕的程式碼給準備準備，分享分享，希望可以得到各位的指正，然後能有一些討論，由於我字太丑就不上傳自己默寫的程式碼了，但還是希望各位潦草寫一遍加深一下印象吧，以上；

Part 1.生產者-消費者問題

這絕對是屬於重點了，不管是考察對於該重要模型的理解還是考察程式碼能力，這都是一道很好的考題，所以很有必要的，我們先來回顧一下什麼是生產者-消費者問題；

問題簡單回顧

生產者消費者問題（英語：Producer-consumer problem），也稱有限緩衝問題（英語：Bounded-buffer problem），是一個多執行緒同步問題的經典案例。該問題描述了共享固定大小緩衝區的兩個執行緒——即所謂的「生產者」和「消費者」——在實際運行時會發生的問題。生產者的主要作用是生成一定量的數據放到緩衝區中，然後重複此過程。與此同時，消費者也在緩衝區消耗這些數據。該問題的關鍵就是要保證生產者不會在緩衝區滿時加入數據，消費者也不會在緩衝區中空時消耗數據。(摘自維基百科：生產者消費者問題)

• 注意： 生產者-消費者模式中的記憶體快取區的主要功能是數據在多執行緒間的共享，此外，通過該緩衝區，可以緩解生產者和消費者的性能差；

幾種實現方式

上面說到該問題的關鍵是：如何保證生產者不會在緩衝區滿時加入數據，消費者也不會在緩衝區空時消耗數據；解決思路可以簡單概括為：

• 生產者持續生產，直到緩衝區滿，滿時阻塞；緩衝區不滿後，繼續生產；
• 消費者持續消費，直到緩衝區空，空時阻塞；緩衝區不空後，繼續消費；
• 生產者和消費者都可以有多個；

那麼在 Java 語言中，能達到上述要求的，自然而然的就會有如下的幾種寫法，但是問題的核心都是能夠讓消費者和生產者在各自滿足條件需要阻塞時能夠起到正確的作用：

• wait()/notify()方式；
• await()/signal()方式；
• BlockingQueue阻塞隊列方式；
• PipedInputStream/PipedOutputStream方式；

手寫程式碼，我們著重掌握上面對應的第一種和第三種寫法就足夠了；

wait()/notify()方式實現

在手寫程式碼之前，我們需要現在 IDE 上實現一遍，理解其中的過程並且找到一些重點/細節，我們先來程式碼走一遍，然後我把我理解的重點給圈兒出來：

生產者程式碼

public class Producer implements Runnable {      private volatile boolean isRunning = true;      private final Vector sharedQueue;                            // 記憶體緩衝區      private final int SIZE;                                      // 緩衝區大小      private static AtomicInteger count = new AtomicInteger();    // 總數，原子操作      private static final int SLEEPTIME = 1000;        public Producer(Vector sharedQueue, int SIZE) {          this.sharedQueue = sharedQueue;          this.SIZE = SIZE;      }        @Override      public void run() {          int data;          Random r = new Random();            System.out.println("start producer id = " + Thread.currentThread().getId());          try {              while (isRunning) {                  // 模擬延遲                  Thread.sleep(r.nextInt(SLEEPTIME));                    // 當隊列滿時阻塞等待                  while (sharedQueue.size() == SIZE) {                      synchronized (sharedQueue) {                          System.out.println("Queue is full, producer " + Thread.currentThread().getId()                                  + " is waiting, size：" + sharedQueue.size());                          sharedQueue.wait();                      }                  }                    // 隊列不滿時持續創造新元素                  synchronized (sharedQueue) {                      data = count.incrementAndGet();                 // 構造任務數據                      sharedQueue.add(data);                      System.out.println("producer create data:" + data + ", size：" + sharedQueue.size());                      sharedQueue.notifyAll();                  }              }          } catch (InterruptedException e) {              e.printStackTrace();              Thread.currentThread().interrupted();          }      }        public void stop() {          isRunning = false;      }  }  

有了上面的提到的解決思路，應該很容易實現，但是這裡主要提一下一些細節和重點：

• 創造數據：生產者-消費者解決的問題就是數據在多執行緒間的共享，所以我們首要關心的問題就應該是數據，我們這裡採用的是使用一個AtomicInteger類來為我們創造數據，使用它的好處是該類是一個保證原子操作的類，我們使用其中的incrementAndGet()方法不僅能夠保證執行緒安全，還可以達到一個計數的效果，所以是一個既簡單又實用的選擇，當然也可以使用其他的數據來代替，這裡注意的是要保證該類在記憶體中只存在一份，使用`static`修飾；
• 記憶體緩衝區：要保證在多執行緒環境下記憶體緩衝區的安全，所以我們考慮使用簡單的Vector類來作為我們的記憶體緩衝區，並且使用final修飾保證記憶體緩衝區的唯一，然後的話我們需要判斷隊列是否滿，需要手動添加一個標識緩衝區大小的變數SIZE，注意也是final修飾；
• 模擬延遲：這裡主要模擬的是一個網路延遲，我們首先定義了一個SLEEPTIME的延遲範圍，注意使用的是`static final`修飾，然後使用Random()類的nextInt()方法來隨機選取一個該範圍內的值來模擬網路環境中的延遲；
• 停止方法：首先需要知道在Thread類中有一個棄用的stop()方法，我們自己增加一個標誌位isRunning來完成我們自己的stop()功能，需要注意的是使用`volatile`來修飾，保證該標誌位的可見性；
• 錯誤處理：當捕獲到錯誤時，我們應該使用Thread類中的interrupted()方法來終止當前的進程；
• 消息提示：我們主要是要在控制台輸出該生產者的資訊，包括當前隊列的狀態，大小，當前執行緒的生產者資訊等，注意的是資訊格式的統一(後面的消費者同樣的)；

消費者程式碼

public class Consumer implements Runnable {        private final Vector sharedQueue;                            // 記憶體緩衝區      private final int SIZE;                                      // 緩衝區大小      private static final int SLEEPTIME = 1000;        public Consumer(Vector sharedQueue, int SIZE) {          this.sharedQueue = sharedQueue;          this.SIZE = SIZE;      }        @Override      public void run() {            Random r = new Random();            System.out.println("start consumer id = " + Thread.currentThread().getId());          try {              while (true) {                  // 模擬延遲                  Thread.sleep(r.nextInt(SLEEPTIME));                    // 當隊列空時阻塞等待                  while (sharedQueue.isEmpty()) {                      synchronized (sharedQueue) {                          System.out.println("Queue is empty, consumer " + Thread.currentThread().getId()                                  + " is waiting, size：" + sharedQueue.size());                          sharedQueue.wait();                      }                  }                    // 隊列不空時持續消費元素                  synchronized (sharedQueue) {                      System.out.println("consumer consume data：" + sharedQueue.remove(0) + ", size：" + sharedQueue.size());                      sharedQueue.notifyAll();                  }              }          } catch (InterruptedException e) {              e.printStackTrace();              Thread.currentThread().interrupt();          }      }  }  

跟生產者相同的，你需要注意記憶體緩衝區/ 模擬延遲/ 錯誤處理/ 消息提示這些方面的細節問題，總體來說消費者就是持續不斷的消費，也比較容易實現；

主執行緒程式碼

有了我們的消費者和生產者程式碼，我們需要來驗證一下它們的正確性，照常理來說我們直接創建一些消費者和生產者的執行緒讓它們執行就可以了啊，但是為了「加分」考慮呢，我們還是使用執行緒池吧..也不是特別複雜：

public static void main(String args[]) throws InterruptedException {      // 1.構建記憶體緩衝區      Vector sharedQueue = new Vector();      int size = 4;        // 2.建立執行緒池和執行緒      ExecutorService service = Executors.newCachedThreadPool();      Producer prodThread1 = new Producer(sharedQueue, size);      Producer prodThread2 = new Producer(sharedQueue, size);      Producer prodThread3 = new Producer(sharedQueue, size);      Consumer consThread1 = new Consumer(sharedQueue, size);      Consumer consThread2 = new Consumer(sharedQueue, size);      Consumer consThread3 = new Consumer(sharedQueue, size);      service.execute(prodThread1);      service.execute(prodThread2);      service.execute(prodThread3);      service.execute(consThread1);      service.execute(consThread2);      service.execute(consThread3);        // 3.睡一會兒然後嘗試停止生產者      Thread.sleep(10 * 1000);      prodThread1.stop();      prodThread2.stop();      prodThread3.stop();        // 4.再睡一會兒關閉執行緒池      Thread.sleep(3000);      service.shutdown();  }  

大家可以自行去看看運行的結果，是沒有問題的，不會出現多生產或者多消費之類的多執行緒問題，運行一段時間等生產者都停止之後，我們可以觀察到控制台三個消費者都在等待數據的情況：

Queue is empty, consumer 17 is waiting, size：0  Queue is empty, consumer 15 is waiting, size：0  Queue is empty, consumer 16 is waiting, size：0  

BlockingQueue阻塞隊列方式實現

該方式對比起上面一種方式實現起來要簡單一些，因為不需要手動的去通知其他執行緒了，生產者直接往隊列中放數據直到隊列滿，消費者直接從隊列中獲取數據直到隊列空，BlockingQueue會自動幫我們完成阻塞這個動作，還是先來看看程式碼

生產者程式碼

public class Producer implements Runnable {      private volatile boolean isRunning = true;      private BlockingQueue<Integer> queue;                        // 記憶體緩衝區      private static AtomicInteger count = new AtomicInteger();    // 總數，原子操作      private static final int SLEEPTIME = 1000;        public Producer(BlockingQueue<Integer> queue) {          this.queue = queue;      }        @Override      public void run() {          int data;          Random r = new Random();            System.out.println("start producer id = " + Thread.currentThread().getId());          try {              while (isRunning) {                  // 模擬延遲                  Thread.sleep(r.nextInt(SLEEPTIME));                    // 往阻塞隊列中添加數據                  data = count.incrementAndGet();                 // 構造任務數據                  System.out.println("producer " + Thread.currentThread().getId() + " create data：" + data                          + ", size：" + queue.size());                  if (!queue.offer(data, 2, TimeUnit.SECONDS)) {                      System.err.println("failed to put data：" + data);                  }              }          } catch (InterruptedException e) {              e.printStackTrace();              Thread.currentThread().interrupted();          }      }        public void stop() {          isRunning = false;      }  }  

跟上面一種方式沒有很大的差別，倒是程式碼更加簡單通透，不過需要注意的是對阻塞隊列添加失敗的錯誤處理；

消費者程式碼

public class Consumer implements Runnable {        private BlockingQueue<Integer> queue;                            // 記憶體緩衝區      private static final int SLEEPTIME = 1000;        public Consumer(BlockingQueue<Integer> queue) {          this.queue = queue;      }        @Override      public void run() {            int data;          Random r = new Random();            System.out.println("start consumer id = " + Thread.currentThread().getId());          try {              while (true) {                  // 模擬延遲                  Thread.sleep(r.nextInt(SLEEPTIME));                    // 從阻塞隊列中獲取數據                  if (!queue.isEmpty()) {                      data = queue.take();                      System.out.println("consumer " + Thread.currentThread().getId() + " consume data：" + data                              + ", size：" + queue.size());                  } else {                      System.out.println("Queue is empty, consumer " + Thread.currentThread().getId()                              + " is waiting, size：" + queue.size());                  }              }          } catch (InterruptedException e) {              e.printStackTrace();              Thread.currentThread().interrupt();          }      }  }  

主執行緒程式碼

public static void main(String args[]) throws InterruptedException {      // 1.構建記憶體緩衝區      BlockingQueue<Integer> queue = new LinkedBlockingDeque<>();        // 2.建立執行緒池和執行緒      ExecutorService service = Executors.newCachedThreadPool();      Producer prodThread1 = new Producer(queue);      Producer prodThread2 = new Producer(queue);      Producer prodThread3 = new Producer(queue);      Consumer consThread1 = new Consumer(queue);      Consumer consThread2 = new Consumer(queue);      Consumer consThread3 = new Consumer(queue);      service.execute(prodThread1);      service.execute(prodThread2);      service.execute(prodThread3);      service.execute(consThread1);      service.execute(consThread2);      service.execute(consThread3);        // 3.睡一會兒然後嘗試停止生產者      Thread.sleep(10 * 1000);      prodThread1.stop();      prodThread2.stop();      prodThread3.stop();        // 4.再睡一會兒關閉執行緒池      Thread.sleep(3000);      service.shutdown();  }  

因為隊列中添加和刪除的操作比較頻繁，所以這裡使用LinkedBlockingQueue來作為阻塞隊列，所以這裡除了記憶體緩衝區有所不同以外，其他的都差不多…當然你也可以指定一個隊列的大小；

總結以及改進

生產者-消費者模式很好地對生產者執行緒和消費者執行緒進行解耦，優化了系統整體的結構，同時由於緩衝區的作用，允許生產者執行緒和消費者執行緒存在執行上的性能差異，從一定程度上緩解了性能瓶頸對系統性能的影響；上面兩種寫法都是非常常規的寫法，只能說能起碼能在及格的基礎上加個那麼點兒分數，如果想要得高分可以去搜索搜搜 Disruptor 來實現一個無鎖的生產者-消費者模型….這裡就不提及了..

改進：上面的執行緒輸出可能會有點兒不友好（不直觀），因為我們這裡是直接使用的執行緒的 ID 來作為輸出，我們也可以給執行緒弄一個名字來作為輸出，以上；

Part 2.排序演算法

排序演算法當然也算是重點考察的對象之一了，畢竟基礎且偏演算法，當然我們有必要去了解常見的排序演算法以及它們採取了怎樣的思想又是如何實現的還有複雜度的問題，但是這裡的話，主要就提及兩種考的比較常見的排序演算法：冒泡和快排，以及分別對它們進行的一些優化；

冒泡排序

冒泡應該是比較基礎的一種演算法，我們以從小到大排序為例，它的基礎思想是：從第一個數開始直到數組倒數第二個數，每一輪都去比較數組中剩下的數，如果後面的數據更小則兩數交換，這樣一輪一輪的比較交換下來，最大的那個數也就「沉到」了數組的最後，最小的「冒」到了數組的最前面，這樣就完成了排序工作；

基礎演算法程式碼（未優化）

很簡單，直接上程式碼：

/**   * 冒泡排序   *   * @param nums 待排序的數組   */  public void bubbleSort(int[] nums) {      // 正確性判斷      if (null == nums || nums.length <= 1) {          return;      }        // 從小到大排序      for (int i = 0; i < nums.length - 1; i++) {          for (int j = i + 1; j < nums.length; j++) {              if (nums[i] > nums[j]) {                  nums[i] = nums[i] + nums[j];                  nums[j] = nums[i] - nums[j];                  nums[i] = nums[i] - nums[j];              }          }      }  }  

這裡需要注意：加上正確性判斷；（討論：其實我看大多數地方都是沒有這個的，不知道有沒有加上的必要…求討論）

另外光寫完實現冒泡排序的演算法是不算完的，還要養成良好的習慣去寫測試單元用例，而且儘可能要考慮到多的點，例如這裡的負數、多個相同的數之類的特殊情況，我就大概寫一個吧，也歡迎指正：

@Test  public void bubbleSortTester() {        // 測試用例1：驗證負數是否滿足要求      int[] nums = {1, 4, 2, -2, 5, 11, -7, 0};      bubbleSort(nums);      // 輸出測試結果      for (int i = 0; i < nums.length; i++) {          System.out.print(nums[i] + ", ");      }      System.out.println();        // 測試用例2：驗證多個相同的數是否滿足要求      nums = new int[]{1, 1, 5, 7, 7, 3, 1};      bubbleSort(nums);      // 輸出測試結果      for (int i = 0; i < nums.length; i++) {          System.out.print(nums[i] + ", ");      }  }  

冒泡排序優化

想像一個這樣的場景：如果該數組基本有序，或者在數組的後半段基本有序，上面的演算法就會浪費許多的時間開銷，所以我們不再使用雙重嵌套去比較每兩個元素的值，而只是不斷比較數組每前後兩個數值，讓大的那個數不斷「冒」到數組的最後，然後縮小尾邊界的範圍，並且增加一個標誌位，表示這一趟是否發生了交換，如果沒有那麼證明該數組已經有序則完成了排序了：

/**   * 改進的冒泡排序   *   * @param nums 待排序的數組   */  public void bubbleSort2(int[] nums) {      // 正確性判斷      if (null == nums || nums.length <= 1) {          return;      }        // 使用一個數來記錄尾邊界      int length = nums.length;      boolean flag = true;// 發生了交換就為true, 沒發生就為false，第一次判斷時必須標誌位true。      while (flag) {          flag = false;// 每次開始排序前，都設置flag為未排序過          for (int i = 1; i < length; i++) {              if (nums[i - 1] > nums[i]) {// 前面的數字大於後面的數字就交換                  int temp;                  temp = nums[i - 1];                  nums[i - 1] = nums[i];                  nums[i] = temp;                    // 表示交換過數據;                  flag = true;              }          }          length--; // 減小一次排序的尾邊界      }  }  

同樣的記得寫單元測試函數；

冒泡排序進一步優化

順著這個思路，我們進一步想像一個場景：現在有一個包含 1000 個數的數組，僅有前面 100 個數無序，後面的 900 個數都比前面的 100 個數更大並且已經排好序，那麼上面優化的方法又會造成一定的時間浪費，所以我們進一步增加一個變數記錄最後發生交換的元素的位置，也就是排序的尾邊界了：

/**   * 冒泡演算法最優解   *   * @param nums 待排序的數組   */  public static void bubbleSort3(int[] nums) {      int j, k;      int flag = nums.length;// flag來記錄最後交換的位置，也就是排序的尾邊界        while (flag > 0) {// 排序未結束標誌          k = flag;// k 來記錄遍歷的尾邊界          flag = 0;            for (j = 1; j < k; j++) {              if (nums[j - 1] > nums[j]) {// 前面的數字大於後面的數字就交換                  // 交換a[j-1]和a[j]                  int temp;                  temp = nums[j - 1];                  nums[j - 1] = nums[j];                  nums[j] = temp;                    // 表示交換過數據;                  flag = j;// 記錄最新的尾邊界.              }          }      }  }  

這應該是最優的冒泡排序了，同時也別忘記了最後要寫測試單元用例程式碼；

快速排序

快排也是一種很經典的演算法，它使用了一種分治的思想，基本思想是：通過一趟排序將待排序的數組分成兩個部分，其中一部分記錄的是比關鍵字更小的，另一部分是比關鍵字更大的，然後再分別對著兩部分繼續進行排序，直到整個序列有序；

基礎實現

非常經典的程式碼，直接上吧：

public static void quickSort(int[] arr) {      qsort(arr, 0, arr.length - 1);  }    private static void qsort(int[] arr, int low, int high) {      if (low < high) {          int pivot = partition(arr, low, high);        // 將數組分為兩部分          qsort(arr, low, pivot - 1);                   // 遞歸排序左子數組          qsort(arr, pivot + 1, high);                  // 遞歸排序右子數組      }  }    private static int partition(int[] arr, int low, int high) {      int pivot = arr[low];               // 樞軸記錄      while (low < high) {          while (low < high && arr[high] >= pivot) --high;          arr[low] = arr[high];           // 交換比樞軸小的記錄到左端          while (low < high && arr[low] <= pivot) ++low;          arr[high] = arr[low];           // 交換比樞軸小的記錄到右端      }      // 掃描完成，樞軸到位      arr[low] = pivot;      // 返回的是樞軸的位置      return low;  }  

當然，在手撕的時候需要注意函數上的 Java Doc 格式的注釋，這裡省略掉是為了節省篇幅，另外別忘了測試單元用例程式碼；

上面的程式碼也很容易理解，其實就是一個「填坑」的過程，第一個「坑」挖在每次排序的第一個位置arr[low]，從序列後面往前找第一個比pivot小的數來把這個「坑」填上，這時候的「坑」就變成了當前的arr[high]，然後再從序列前面往後用第一個比pivot大的數把剛才的「坑」填上，如此往複，始終有一個「坑」需要我們填上，直到最後一個「坑」出現，這個「坑」使用一開始的pivot填上就可以了，而這個「坑」的位置也就是pivot該填上的正確位置，我們再把這個位置返回，就可以把當前序列分成兩個部分再依次這樣操作最終就達到排序的目的了，不得不說這樣的思想挺神奇的；

演算法優化

上面這個快速排序演算法可以說是最基本的快速排序，因為它並沒有考慮任何輸入數據。但是，我們很容易發現這個演算法的缺陷：這就是在我們輸入數據基本有序甚至完全有序的時候，這演算法退化為冒泡排序，不再是O(n㏒n)，而是O(n^2)了。

究其根源，在於我們的程式碼實現中，每次只從數組第一個開始取。如果我們採用「三者取中」，即 arr[low], arr[high], arr[(low+high)/2] 三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們仍然無法將它在數組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。

此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級別。但是，如果每次劃分的兩個數組長度嚴重失衡，則為最壞情況，棧的深度將增加到O(n)。此時，由棧空間帶來的空間複雜度不可忽略。如果加上額外變數的開銷，這裡甚至可能達到恐怖的O(n^2)空間複雜度。所以，快速排序的最差空間複雜度不是一個定值，甚至可能不在一個級別。

為了解決這個問題，我們可以在每次劃分後比較兩端的長度，並先對短的序列進行排序（目的是先結束這些棧以釋放空間），可以將最大深度降回到O(㏒n)級別。

關於優化的話，了解一個大概的思路就可以了，那在這裡稍微總結一下：

• ①三數取中作為樞軸記錄；
• ②當待排序序列的長度分割到一定大小之後，使用插入排序；
• ③在一次分割結束後，可以把與pivot相等的元素聚在一起，繼續下次分割時，不用再對與pivot相等的元素分割；
• ④優化遞歸操作；

參考文章：http://blog.51cto.com/flyingcat2013/1281614 想要了解的更多的童鞋可以戳這裡：https://blog.csdn.net/insistGoGo/article/details/7785038

Part 3.二叉樹相關演算法

二叉樹也是一個容易提及的概念和寫演算法的問題，特別是它的幾種遞歸遍歷和非遞歸遍歷，都是基礎且常考的點，那在這裡就稍微整理整理吧…

二叉樹的幾種遞歸遍歷

前序、中序、後序遍歷都是非常基礎且容易的遍歷方法，重點還是在後面的中序和後續的非遞歸遍歷上，當然還有層序遍歷，所以這裡不多說，直接給程式碼；

前序遍歷遞歸實現

public void preOrderTraverse1(TreeNode root) {      if (root != null) {          System.out.print(root.val + "  ");          preOrderTraverse1(root.left);          preOrderTraverse1(root.right);      }  }  

中序遍歷遞歸實現

public void inOrderTraverse1(TreeNode root) {      if (root != null) {          preOrderTraverse1(root.left);          System.out.print(root.val + "  ");          preOrderTraverse1(root.right);      }  }  

後序遍歷遞歸實現

public void postOrderTraverse1(TreeNode root) {      if (root != null) {          preOrderTraverse1(root.left);          preOrderTraverse1(root.right);          System.out.print(root.val + "  ");      }  }  

前面三種遍歷，也就是輸出結點數據的位置不同而已，所以很容易，但是如果手寫，建議問清楚面試官要求，是在遍歷時直接輸出還是需要函數返回一個List集合，然後注意寫測試用例程式碼！

二叉樹的幾種非遞歸遍歷

★★層序遍歷★★

層序遍歷我們只需要增加使用一個隊列即可，看程式碼很容易理解：

public void levelTraverse(TreeNode root) {      if (root == null) {          return;      }      LinkedList<TreeNode> queue = new LinkedList<>();      queue.offer(root);      while (!queue.isEmpty()) {          TreeNode node = queue.poll();          System.out.print(node.val + "  ");          if (node.left != null) {              queue.offer(node.left);          }          if (node.right != null) {              queue.offer(node.right);          }      }  }  

前序遍歷非遞歸實現

public void preOrderTraverse2(TreeNode root) {      if (root == null) {          return;      }      LinkedList<TreeNode> stack = new LinkedList<>();      TreeNode pNode = root;      while (pNode != null || !stack.isEmpty()) {          if (pNode != null) {              System.out.print(pNode.val + "  ");              stack.push(pNode);              pNode = pNode.left;          } else { //pNode == null && !stack.isEmpty()              TreeNode node = stack.pop();              pNode = node.right;          }      }  }  

★★中序遍歷非遞歸實現★★

/**   * 非遞歸中序遍歷二叉樹   *   * @param root 二叉樹根節點   * @return 中序遍歷結果集   */  public List<Integer> inorderTraversal(TreeNode root) {        List<Integer> list = new ArrayList<>();      ArrayDeque<TreeNode> stack = new ArrayDeque<>();        while (root != null || !stack.isEmpty()) {          while (root != null) {              stack.addFirst(root);              root = root.left;          }          root = stack.removeFirst();          list.add(root.val);          root = root.right;      }      return list;  }  

★★後續遍歷非遞歸實現★★

/**   * 二叉樹的後序遍歷   *   * @param root 二叉樹根節點   * @return 後序遍歷結果集   */  public List<Integer> postorderTraversal(TreeNode root) {      List<Integer> list = new ArrayList<>();      Deque<TreeNode> stack = new ArrayDeque<>();      TreeNode pre = null;      while (!stack.isEmpty() || root != null) {            while (root != null) {              stack.push(root);              root = root.left;          }            root = stack.peek();          // i ：判斷如果右子樹不為空且不為          if (root.right != null && root.right != pre) {              root = root.right;          } else {              root = stack.pop();              list.add(root.val);              pre = root;              root = null;          }      }      return list;  }  

如果比較難以理解的話，可以自己嘗試著跟跟 Debug 然後看看過程；

二叉樹相關其他演算法題

另外的話還有一些比較常見的關於樹的演算法，在文章的末尾，這裡就不再贅述了：

鏈接：https://www.jianshu.com/p/4ef1f50d45b5

Part 4.其他重要演算法

除了上面 3 Part 比較重要的點之外，還有一些其他的演算法也是經常考到的，下面我們來說；

1.反轉鏈表

這是一道很經典的題，不僅考你對鏈表的理解，而且還有一些細節（例如正確性判斷/ 測試用例）需要你從程式碼層面去展現，下面我們給出兩段程式碼，讀者可以自行去比較，我只是提供一個思路；

思路一：使用一個 Node 不斷鏈接

這是最經典的演算法，也是需要我們牢牢掌握的方法，最重要的還是理解 while() 循環中的過程：

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

思路二：反轉元素值然後重新賦給 Node

這是一個很簡單的思路，比上個思路要多遍歷一遍鏈表，但是好處是簡單，思路清晰，實現起來容易，emm，像這一類問題我覺得另一個比較重要的就是舉一反三的能力吧，在這裡我只提供兩個思路，其實還有很多種實現方法，當然也別忘了細節的東西~

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

2.合併兩個有序鏈表

問題描述：將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的；

同樣的經典演算法，需要掌握：

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

這道題也是 LeetCode 上的一道題，我當時的做法是下面這樣的，雖然看起來程式碼量多了不少而且看起來蠢蠢的..但是經過 LeetCode 測試，甚至比上面的實現要快上那麼 2ms，特別提醒：下面的程式碼只是用作一個思路的參考，著重掌握上面的程式碼 ：

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

3.兩個鏈表的第一個公共結點

題目描述：找出兩個鏈表的第一個公共結點；

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

需要注意的細節是：①正確性判斷；②判斷鏈表是否自己成環；③注釋；④注意要自己寫測試用例啊…

另外還有一些類似的題目像是：①鏈表入環結點；②鏈表倒數第k個結點；之類的都是需要掌握的…

4.二分查找演算法

二分查找也是一類比較常考的題目，其實程式碼也比較容易理解，直接上吧，再再再提醒一下：注意正確性判斷還有測試用例…

普通實現

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

遞歸實現

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

5.斐波那契數列

這也是一道很經典的題，通常是要要求 N 值的範圍的，常規寫法應該很簡單，所以需要掌握的是優化之後的演算法：

公眾號字數限制，詳情戳：https://www.jianshu.com/p/3f0cd7af370d  

還是注意正確性判斷然後寫測試用例…

手撕程式碼總結

如果用手寫程式碼的話，確實是個挺麻煩的事兒，首先需要對程式碼有相當的熟悉程度，然後其次的話考察的都是一些細節的東西，例如：

• 編碼規範：包括一些命名的規範/ 注釋的規範等等；
• 縮進：這個我自己倒是挺在意的..關於這個可以去參考參考阿里出的那個規範手冊；
• 注釋：如果命名規範做得好的話其實是可以達到程式碼即注釋的，但是仍然有一些需要標註的地方例如函數頭之類的，最好還是做好注釋；
• 程式碼的完整性：我覺得這個包括對於錯誤的處理/ 正確性判斷這樣一類的東西；
• 測試用例：每個函數都需要一定的測試來保證其正確性，所以這個還是挺有必要的，特別是一些邊界情況，null 值判斷之類的；
• 想好再下筆：這一點其實也蠻重要的，不管是在紙上還是在我們平時的編程中，思路永遠都是更重要的；

說來說去還是關於程式碼的事，我覺得還是理清思路最重要，所以我們需要在一遍一遍熟悉程式碼的過程中，熟知這些程式碼的思路，只有搞清楚這些程式碼背後的原理了，我們才能正確且快速的寫出我們心中想要的程式碼，而不是簡單的去背誦，這樣是沒有很大效果的，以上