不一样的二叉树非递归遍历

本篇将讨论模拟系统栈的二叉树非递归遍历，并由此讨论一般化的将递归程序改为非递归程序的方式。

二叉树的非递归遍历

就以中序遍历为例，下面是大家都熟悉的前序遍历递归版本代码框架：

void inOrder(TreeNode *root){
    if(root == NULL) return;
    inOrder(root->left);
    visit(root);
    inOrder(root->right);
}

计算机执行递归程序从操作系统角度看实际上还是一个函数调用另一个函数，只不过调用的函数是这个程序本身而已，所以需要在调用前记录当前程序执行到哪里，以及当前程序的变量状态，将这些信息压入系统栈，这样当递归调用返回时就能继续执行当前应该执行的逻辑。
下面我们将按照模拟系统栈的方式将其改为非递归形式，所谓模拟系统栈，就是模拟计算机执行递归程序时的过程，使用的是自己定义的栈来记录需要的信息。
第一步：为程序分段
为什么要分段，是因为递归程序执行到不同阶段需要保存相应的信息以方便在递归返回时继续执行当前程序，我们想要明白应该保存哪些位置的信息最好方式就是对程序分段。

void inOrder(TreeNode *root){
    // pos: 0
    if(root == NULL) return;
    inOrder(root->left);
    // pos: 1
    visit(root);
    inOrder(root->right);
    // pos: 2
}

为递归程序分段的原则是程序会从哪里开始和哪里可能会发生递归函数的调用，可以看到我们为程序标注了pos0，pos1，pos2的分段，因为该程序执行时会从pos0进入，然后到pos1前的inorder(root->left)发生了一次调用递归函数，所以在递归调用前要将当前信息保存到栈中；同理在pos2前的inorder(root->right)发生了一次调用，所以在调用之前要将信息保存到栈中。
第二步：确定要保存的信息
明白了在哪些位置保存信息到栈中接下来就是看我们需要保存什么信息了，对于二叉树遍历其实就是程序当前执行到的位置和当前正在访问的节点两个信息，这两个信息唯一确定了递归函数状态。
于是给出非递归代码：

struct state {
    // 首先定义状态结构体（当然使用数组也是可以的）
    int pos; // 记录状态：程序执行到的位置
    TreeNode* node; // 记录状态：当前访问的节点
};
void inorder(TreeNode* root) {
    stack<state>s;
    s.push({0, root});
    while (s.size()) {
        auto a = s.top();
        s.pop();
        if (a.pos == 0) {
            if (a.node == NULL) continue; 
            a.pos = 1;
            s.push(a);
            s.push({ 0, a.node->left });
        }
        else if (a.pos == 1) {
            visit(a.node);
            a.pos = 2; s.push(a); 
            s.push({ 0, a.node->right });
        }
        else if (a.pos == 2) continue;
    }
    return;
}

注意到在pos2之后其实没有新的逻辑了，所以程序可以简化一些，将pos2信息的入栈代码部分删去(实际中为了逻辑清晰最好不删)：

void inorder(TreeNode* root) {
    stack<state>s;
    s.push({0, root});
    while (s.size()) {
        auto a = s.top();
        s.pop();
        if (a.pos == 0) {
            if (a.node == NULL) continue; 
            a.pos = 1;
            s.push(a);
            s.push({ 0, a.node->left });
        }
        else if (a.pos == 1) {
            visit(a.node);
            s.push({ 0, a.node->right });
        }
    }
    return;
}

好了，这就是模拟系统栈的非递归代码。
这样做有什么好处呢，一个好处是非递归程序相对于递归程序都具有的好处，递归程序在执行过程中中间信息是保存在系统栈中的，系统栈大小有限，递归层次太深会引起栈溢出，但非递归程序可以一定程度上避免这个问题，另外递归程序返回时有额外开销，时间效率实际也略低于非递归程序；另一个好处是针对代码本身的，模拟系统栈帮助我们明白了递归程序的本质，这会让我们写出更结构化的非递归代码，怎么理解这一点呢？还记得数据结构课本里的二叉树遍历的普通的非递归代码吗，前序和中序非递归的逻辑差不太多，但是对于非递归后序遍历代码却变的复杂一些，这样就要用两套模式来记忆和理解二叉树的非递归。但是基于模拟系统栈理解了递归的本质，用该方式来书写非递归代码就只需要一套模式，后序遍历分段：

void postorder(TreeNode* root) {
    // pos0
    if (root == NULL) return;
    postorder(root->left);
    // pos1
    postorder(root->right);
    // pos2
    visit(root);
}

于是后序遍历的非递归版本：

void postorder(TreeNode* root) {
    stack<state>s;
    s.push({0,root});
    while (s.size()) {
        auto a = s.top();
        s.pop();
        if (a.pos == 0) {
            if (a.node == NULL) continue; 
            a.pos = 1;
            s.push(a);
            s.push({ 0,a.node->left });
        }
        else if (a.pos == 1) {
            a.pos = 2; s.push(a); 
            s.push({ 0, a.node->right });
        }
        else if (a.pos == 2) visit(a.node);
    }
    return;
}

相应的前序非递归版本：

void preorder(TreeNode* root) {
    stack<state>s;
    s.push({0,root});
    while (s.size()) {
        auto a = s.top();
        s.pop();
        if (a.pos == 0) {
            if (a.node == NULL) continue; 
            visit(a.node);
            a.pos = 1;
            s.push(a);
            s.push({ 0,a.node->left });
        }
        else if (a.pos == 1) {
            a.pos = 2; s.push(a); 
            s.push({ 0, a.node->right });
        }
        else if (a.pos == 2) continue;
    }
    return;
}

可以看到，在模拟系统栈的方式下，前中后序的非递归遍历仅仅取决于要实现访问的逻辑所在的位置，代码在形式上完全统一，妙啊！

另一个例子

以一个具体问题为例，再来看看如何模拟系统栈实现递归到非递归程序的转化：
题目：组合型枚举
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。
数据范围
n>0 , 0≤m≤n , n+(n−m)≤25
输入样例：

5 3

输出样例：

思考题：如果要求使用非递归方法，该怎么做呢？
思路分析和代码：
实现这样的枚举本身并不太难，结合位运算，用state来表示是否选择某个数，初值为1<<n，第i位为1表示选择该位对应的数，为0表示不选。那么当state的二进制表示中有m个1时，即是一个组合。于是给出递归版本代码：

# include<iostream>
# include<stack>
using namespace std;
int n, m;
void dfs(int u, int count, int state) {
    // 当前考虑第u个
    if (count + n - u < m)return;//当前往后都选上也不够m个
    if (count == m) {
        for (int i = 0; i < n; i++)
            if (state & (1 << i))
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    dfs(u + 1, count + 1, state | (1 << u));//用u,state第u位置1
    dfs(u + 1, count, state); // 不用u
}
int main(){
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

对递归代码分段：

void dfs(int u, int count, int state) {
    // 0
    if (count + n - u < m)return;//当前往后都选上也不够m个
    if (count == m) {
        for (int i = 0; i < n; i++)
            if (state & (1 << i))
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    dfs(u + 1, count + 1, state | (1 << u));//用u,state第u位置1
    // 1
    dfs(u + 1, count, state); // 不用u
    // 2
}

给出非递归代码：

# include<iostream>
# include<stack>
using namespace std;
int n, m;
// 栈模拟递归
struct State {
    int pos, u, count, state;
};
int main() {
    cin >> n >> m;
    stack<State>stk;
    stk.push({ 0,0,0,0 });
    while (stk.size()) {
        auto a = stk.top();
        stk.pop();
        if (a.pos == 0) {
            if (a.count + n - a.u < m)continue;
            if (a.count == m) {
                for (int i = 0; i < n; i++)
                    if ((a.state >> i) & 1)
                        cout << i + 1 << " ";
                cout << endl;
                continue;
            }
            a.pos = 1; 
            stk.push(a);// 原状态保存
            stk.push({ 0,a.u + 1,a.count + 1,a.state | (1 << a.u) });// 加入新状态
        }
        else if (a.pos == 1) {
            a.pos = 2; stk.push(a);// 本行代码可以省略，因pos=2时什么都没做，如果pos=2有其它操作不可省略
            stk.push({0,a.u+1,a.count,a.state});
        }
        else continue;
    }
    return 0;
}

最后总结将递归程序改为非递归的步骤：

1. 对程序分段，明确会在哪些位置发生调用
1. 明确要保存的信息，一般是程序执行到的位置和程序传入的参数
1. 逐语句翻译递归程序