二叉树的前中后序遍历

二叉树的前序、中序、后序遍历是我们学习二叉树的第一节课。那么如何写出易于理解的代码呢？以下的思路是我最近再次思考的结果。

二叉树的前中后序的递归遍历很简单，如下

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

void pre_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->val << " ";
    pre_order_recur(root->left);
    pre_order_recur(root->right);
}

// 左根右
void in_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    in_order_recur(root->left);
    std::cout << root->val << " ";
    in_order_recur(root->right);
}

// 左右根
void post_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    post_order_recur(root->left);
    post_order_recur(root->right);
    std::cout << root->val << " ";
}

那么我们就递归代码改造成非递归就可以解决问题。递归的本质是在系统栈上存储我们想要的数据，那么我们可以自己构造栈，将数据存储到我们自己的栈上。因此系统栈本身除了保存我们想要的数据外，还有其他比如寄存器指针、函数地址等等额外的数据，导致占用过多的内存空间。于是，我们的非递归代码的主要逻辑是找到需要保存的我们需要的数据。

如上的三种遍历，其实系统栈上都保存了相同的数据，即当前节点，延伸出来的当前节点的值、左指针、右指针。只不过打印位置的不同导致我们想要的数据要保留的时间也不同。

非递归的前序遍历。我们是在开始的时候就打印当前节点的值，然后遍历左子树、右子树。而且重要的是，子树与子树之间是独立的。即永远先是根，然后是子树。而且在遍历子树的时候与之前的根一点关系都没有。因此栈中只需要存储当前节点即可。因为栈的先进后出的性质，所以在实现的时候即为先看右子树、再看左子树。如下实现：

void pre_order_recur_02(TreeNode* root) {
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        std::cout << node->val << " ";
        if (node->right) {
            st.push(node->right);
        }
        if (node->left) {
            st.push(node->left);
        }
    }
    std::cout << std::endl;
}

非递归的中序遍历。刚才说到，前序遍历某一个节点时，此时与他的父节点（根节点）没有一点关系。那么我们再来想，中序遍历时某一个子节点时，与根节点是否有关系呢？答案是有关系。因为我们需要左子树遍历完之后再遍历根节点，最后遍历右子树。因此我们这里需要从递归本身来看。中序遍历我们首先要遍历左子树，在左子树中依旧是先遍历左子树，在遍历根，有没有发现，我们只需要一直遍历左子树，并将其插入栈中，直到某个节点没有左子树，我们就遍历他，并弹出。此时弹出的节点一定是左子节点或者相对的根节点。并且满足遍历顺序，之后，我们在来看弹出的这个节点是否有右子树。对这个右子树继续进行前述的规则即可。

void in_order_recur_02(TreeNode* root) {
    std::stack<TreeNode*> st;
    while (root) {
        st.push(root);
        root = root->left;
    }
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        std::cout << node->val << " ";
        if (node->right) {
            TreeNode* right_node = node->right;
            while (right_node) {
                st.push(right_node);
                right_node = right_node->left;
            }
        }
    }
    std::cout << std::endl;
}

非递归的后序遍历。后序遍历往往搞的很难。这次我们尝试拆分递归的方式完成一个简单的后序遍历。从递归版的后序遍历来看，系统栈上保留的数据也是当前节点，以及当前节点的左节点、右字节、以及当前节点的值。因为当前节点有指针指向左右节点，所以我们只需要记录当前节点即可。后序遍历是先左子树、再右子树，再跟节点。那么我们对于一个节点，按照机器的思路来想，我们先插入一个节点到栈中，然后去检查左子节点，不为空则插入栈中，直到节点的左子节点为空，这时，需要看这个节点的右子节点。那么什么时候要看这个节点的左子节点，什么时候要看这个节点右子节点，以及什么时候要输出这个节点的值，变成了一个问题。我们可以发现，递归的实现中已经定义了这个顺序，但是非递归中我们需要自己存储这个顺序，也就是这个节点的状态。如下代码

enum State { LEFT = 0, RIGHT, OUT };
struct Elem {
    TreeNode* node;
    State state;

    Elem(TreeNode* node, State state) : node(node), state(state) {}
};

void post_order_recur_02(TreeNode* root) {
    std::stack<std::shared_ptr<Elem>> st;
    st.push(std::make_shared<Elem>(root, LEFT));
    while (!st.empty()) {
        // 记住：这里如果是常规类型就是复制，下面的改动不会改到原数据
        auto elem = st.top();
        if (elem->state == LEFT) {
            elem->state = RIGHT;
            if (elem->node->left) {
                st.push(std::make_shared<Elem>(elem->node->left, LEFT));
                continue;
            }
        }
        if (elem->state == RIGHT) {
            elem->state = OUT;
            if (elem->node->right) {
                st.push(std::make_shared<Elem>(elem->node->right, LEFT));
                continue;
            }
        }
        if (elem->state == OUT) {
            std::cout << elem->node->val << " ";
            st.pop();
        }
    }
    std::cout << std::endl;
}

注意，我们遍历这个节点的时候，有时候只是改一下状态，并不弹出，因此要存储指针，可以改到原数据。