假設來到阿里巴巴面試，面試官可能就會讓你反轉下二叉樹鏡像。請大家先思考下，怎么實現(xiàn)？

（1）命令式編程思維

一種實現(xiàn)方式是這樣的：

Node invertTree(root){
 if (root is null){
   return null;
 }
  
 root.left = invertTree(root.right);
 root.right = invertTree(root.left);
  
 return root;
}

我們首先判斷節(jié)點是否為空，如果為空則直接拋出；然后翻轉右樹放置在左邊；翻轉左樹放置在右邊。

這其實是一種命令式編程方式，即我們把要做的事情，以步驟的形式描述出來，然后交給機器去執(zhí)行。

這也正是命令式編程的理論模型——圖靈機的特點。一條寫滿數(shù)據(jù)的紙帶，一條根據(jù)紙帶內容運動的機器，機器的每一步都需要在紙帶上寫出命令。

圖靈機指的是一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態(tài)，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息（命令），然后結合自己的內部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉換自己的內部狀態(tài)，然后進行移動。

（2）函數(shù)式編程思維

函數(shù)式思維提供了另一種思維途徑——翻轉二叉樹，我們可以看做是要得到一顆和原來二叉樹對稱的新二叉樹。這顆新二叉樹的特點是每一個節(jié)點都遞歸地和原樹相反。

Node invert(node){
  if (node is null) {
      return null;
  } else {
      return new Tree(node.value, invert(node.right), invert(node.left));
  }
}

這段代碼體現(xiàn)的思維是舊樹到新樹的映射。對一顆二叉樹而言，它的鏡像樹就是左右節(jié)點遞歸鏡像的樹。

同樣是翻轉二叉樹，但這段代碼得到結果的方式和之前的命令編程模式有本質的差別：通過描述一個 舊樹->新樹 的映射，而不是描述「從舊樹得到新樹應該怎樣做」來達到目的。

世界的兩部分好像在照鏡子，就稱為鏡像世界。

函數(shù)式編程思維：描述舊樹到新樹的映射關系。

命令式編程思維：描述從舊樹得到新樹應該怎樣做。