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

（1）命令式編程思維

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

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

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

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

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

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

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

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

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

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

同樣是翻轉(zhuǎn)二叉樹，但這段代碼得到結(jié)果的方式和之前的命令編程模式有本質(zhì)的差別：通過描述一個(gè) 舊樹->新樹 的映射，而不是描述「從舊樹得到新樹應(yīng)該怎樣做」來達(dá)到目的。

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

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

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