博客

二叉树的遍历有三种经典方式：前序遍历、中序遍历、后序遍历。

递归遍历

递归的写法非常简单：

前序遍历

void preorder_traverse(tree_node* root) {
    if (root == nullptr)  
        return;
    this->preorder.push_back(root->value);
    preorder_traverse(root->left);  
    preorder_traverse(root->right);  
}

中序遍历

void inorder_traverse(tree_node* root) {
    if (root == nullptr)  
        return;
    inorder_traverse(root->left);  
    this->inorder.push_back(root->value); 
    inorder_traverse(root->right);
}

后序遍历

void postorder_traverse(tree_node* root) {
    if (root == nullptr)  
        return;
    postorder_traverse(root->left);  
    postorder_traverse(root->right);  
    this->postorder.push_back(root->value);  
}

非递归的深度优先遍历

二叉树的非递归遍历是一个经典问题，有教科书式的完美解法，但相信很多人和我一样：书打开，“嗯。。马冬梅”，等到要用的时候（比如说面试），“马什么梅来着。。？”。递归的算法很容易记住，试想，如果我们能够根据递归的算法写出非递归的算法，这个问题不就迎刃而解了么~现在，这个问题转化成了——给定任意一个递归算法，如何写出其非递归版本？其实，递归也是函数调用的一种，只不过递归调用的是这个函数本身。让我们来回忆一下操作系统是如何处理函数调用的：

当发生函数调用时，系统暂存当前的系统状态（将当前系统状态压栈），开始执行子函数，待子函数执行完毕后，再从系统栈顶读取之前保存的系统状态，继续主函数的执行。

这为我们模拟系统栈递归函数非递归化提供了一些思路。下面，我们就二叉树遍历中最难非递归化的后序遍历为例，来说明如何模拟系统栈将该递归算法非递归化。再看一眼后序遍历的递归算法：

1 void postorder_traverse(tree_node* root) {
2    if (root == nullptr)  
3        return;
4    postorder_traverse(root->