二叉樹的遍歷早已成為廣大公司的面試題之一，可是僅此一題卻可將面試者技術水平進行更多層次的劃分。

二叉樹遍歷的考核也不僅僅在於考驗被面試者的遞歸思想，還包含了更多的內容，我們慢慢道來。

題面

假設，我們的二叉樹節點結構定義如下：

<code>typedef struct bin_node_s {
  struct bin_node_s *left;
  struct bin_node_s *right;
} bin_node_t;/<code>

請編寫程序遍歷這棵二叉樹。

解題

首先，要弄懂何為二叉樹。顧名思義，二叉樹就是一種一個節點有兩棵子樹的樹結構，兩棵子樹分別稱為左子樹和右子樹。

那麼遍歷這樣一棵二叉樹的代碼該如何寫呢？相信很多人都會馬上給出如下答案：

<code>void traverse(bin_node_t *root)
{
  if (root == NULL)
    return;
  traverse(root->left);
  traverse(root->right);
}/<code>

很好，如果這道題滿分100分，那麼到此其實也只是60分的及格分。

更進一步

為何上面的回答只能給60分，原因是：這個回答僅僅只表示面試者知道二叉樹，且能夠利用基本的遞歸思維完成樹的遍歷。

但是，實際工作中有時我們會對系統性能有更高的追求。那麼我們的問題也就變成了，有沒有可能進一步優化二叉樹遍歷的代碼。

答案必然是有的。

我們可以看到，在這樣一個函數中，有著兩次函數調用。默認的C調用約定會在call指令和ret指令前後向系統棧中壓入或者彈出一些必要信息（請自行查閱C調用約定的內容）。因此可以想見，這段代碼執行時將充斥著壓棧彈棧操作。

這意味著什麼呢？讀者可以自行嘗試使用循環和遞歸兩種方式逆轉單鏈表的時間開銷。很顯然，循環的方式中並不存在頻繁壓棧彈棧很多數據，因此效率遠高於遞歸方式。但這與二叉樹遍歷有什麼關係呢？

讀者是否思考過，最後一個遞歸調用的必要性？或者說，最後一個遞歸調用是想完成什麼功能？

在我們的代碼中，這個遞歸調用僅僅是把root的右子樹right作為一個局部的根結點繼續使用traverse函數進行遍歷。但是，在這一步遞歸之後，root指針我們還有用到嗎？很顯然，沒有。那麼為什麼不嘗試複用root指針呢？而複用root指針代碼會變成什麼樣呢？參見如下：

<code>void traverse(bin_node_t *root)
{
  while (root != NULL) {
    traverse(root->left);
    root = root->right;
  }
}/<code>

最後一個遞歸調用被變換為循環。

如果樹的深度足夠深，那麼我們將極大地節省了壓棧彈棧的開銷。到此，才算是滿分作答。

其實，這種優化方法在《算法導論》中給出過，稱為消除尾遞歸。

閱讀更多 碼哥比特 的文章

關鍵字: 解法 人生第一份工作 遍歷