二叉树遍历的最优解法

二叉树的遍历早已成为广大公司的面试题之一，可是仅此一题却可将面试者技术水平进行更多层次的划分。

二叉树遍历的考核也不仅仅在于考验被面试者的递归思想，还包含了更多的内容，我们慢慢道来。

题面

假设，我们的二叉树节点结构定义如下：

typedef struct bin_node_s {
  struct bin_node_s *left;
  struct bin_node_s *right;
} bin_node_t;

请编写程序遍历这棵二叉树。

解题

首先，要弄懂何为二叉树。顾名思义，二叉树就是一种一个节点有两棵子树的树结构，两棵子树分别称为左子树和右子树。

那么遍历这样一棵二叉树的代码该如何写呢？相信很多人都会马上给出如下答案：

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

很好，如果这道题满分100分，那么到此其实也只是60分的及格分。

更进一步

为何上面的回答只能给60分，原因是：这个回答仅仅只表示面试者知道二叉树，且能够利用基本的递归思维完成树的遍历。

但是，实际工作中有时我们会对系统性能有更高的追求。那么我们的问题也就变成了，有没有可能进一步优化二叉树遍历的代码。

答案必然是有的。

我们可以看到，在这样一个函数中，有着两次函数调用。默认的C调用约定会在call指令和ret指令前后向系统栈中压入或者弹出一些必要信息（请自行查阅C调用约定的内容）。因此可以想见，这段代码执行时将充斥着压栈弹栈操作。

这意味着什么呢？读者可以自行尝试使用循环和递归两种方式逆转单链表的时间开销。很显然，循环的方式中并不存在频繁压栈弹栈很多数据，因此效率远高于递归方式。但这与二叉树遍历有什么关系呢？

读者是否思考过，最后一个递归调用的必要性？或者说，最后一个递归调用是想完成什么功能？

在我们的代码中，这个递归调用仅仅是把root的右子树right作为一个局部的根结点继续使用traverse函数进行遍历。但是，在这一步递归之后，root指针我们还有用到吗？很显然，没有。那么为什么不尝试复用root指针呢？而复用root指针代码会变成什么样呢？参见如下：

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

最后一个递归调用被变换为循环。

如果树的深度足够深，那么我们将极大地节省了压栈弹栈的开销。到此，才算是满分作答。

其实，这种优化方法在《算法导论》中给出过，称为消除尾递归。