另一种二叉树非递归遍历的实现

这是今天在LeetCode上写二叉树后序遍历时突然想到的解法。

众所周知，二叉树的递归遍历十分简单，只有短短几行代码，而且三种遍历方式的代码几乎相同。而传统非递归方法的遍历无论是从代码上，还是理解上，都比递归方法要麻烦不少，尤其是后序遍历最为麻烦。为什么非递归版本的代码就不能像递归版本那样优美呢？其实，非递归版本也是可以做到的。

下面给出我的二叉树前中后序非递归遍历的代码，前序和后序在LeetCode上都通过了评测，如有错误，欢迎大牛指出。

#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    vector<int> vec;
    vector<int> preorderTraversal(TreeNode *root) {
        stack<pair<int, TreeNode*> > st;
        vec.clear();
        st.push(make_pair(1,root));
        while (!st.empty()) {
            pair<int, TreeNode*> p = st.top(); st.pop();
            TreeNode *node = p.second;
            if (node == NULL) continue;
            if (p.first == 0)
                vec.push_back(node->val);
            else {
                st.push(make_pair(1, node->right));
                st.push(make_pair(1, node->left));
                st.push(make_pair(0, node));
            }
        }
        return vec;
    }
    vector<int> inorderTraversal(TreeNode *root) {
        stack<pair<int, TreeNode*> > st;
        vec.clear();
        st.push(make_pair(1,root));
        while (!st.empty()) {
            pair<int, TreeNode*> p = st.top(); st.pop();
            TreeNode *node = p.second;
            if (node == NULL) continue;
            if (p.first == 0)
                vec.push_back(node->val);
            else {
                st.push(make_pair(1, node->right));
                st.push(make_pair(0, node));
                st.push(make_pair(1, node->left));
            }
        }
        return vec;
    }
    vector<int> postorderTraversal(TreeNode *root) {
        stack<pair<int, TreeNode*> > st;
        vec.clear();
        st.push(make_pair(1,root));
        while (!st.empty()) {
            pair<int, TreeNode*> p = st.top(); st.pop();
            TreeNode *node = p.second;
            if (node == NULL) continue;
            if (p.first == 0)
                vec.push_back(node->val);
            else {
                st.push(make_pair(0, node));
                st.push(make_pair(1, node->right));
                st.push(make_pair(1, node->left));
            }
        }
        return vec;
    }
};

可以看到，前中后序遍历的代码仅仅是st.push(make_pair(0, node))这行代码的位置有所变化，算法的时间复杂度和空间复杂度都是O(N)。其中pair中的第一个数表示操作类型，0代表的是打印值操作，1代表的是遍历操作。

程序的原理并不难理解，了解递归的人应该都知道，递归实际上就是一个压栈出栈的过程，程序正是模拟了这一过程。拿后序递归遍历来说，由遍历左子树、遍历右子树、打印值三个操作组成，我们可以反过来依次将打印值、遍历右子树、遍历左子树三个操作压入栈中，之后遍历左子树操作首先出栈，做完遍历左子树操作后，遍历右子树操作出栈，操作完成后打印值值操作出栈，最后程序执行完毕，这个过程和递归的过程实际上是完全一样的。

最后附上我的传统非递归版本的代码作为比较，其实前序和中序都是蛮简单的，一个在入栈时打印，一个在出栈时打印，后序要麻烦些，我们可以注意到在后序遍历中一个点如果要被打印，那么要么它是叶子节点，要么它的右孩子为空并且左孩子刚刚被打印，要么它的右孩子刚刚被打印，根据这个特点就可以写出非递归后序遍历的算法了，另外就是要注意后序遍历要在打印后才能出栈。

class Solution {
public:
    vector<int> vec;
    vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vec.clear();
        TreeNode *T = root;
        while (T || !st.empty()) {
            if (T) {
                vec.push_back(T->val);
                st.push(T);
                T = T->left;
            } else {
                T = st.top(); st.pop();
                T = T->right;
            }
        }
        return vec;
    }
    vector<int> inorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vec.clear();
        TreeNode *T = root;
        while (T || !st.empty()) {
            if (T) {
                st.push(T);
                T = T->left;
            } else {
                T = st.top(); st.pop();
                vec.push_back(T->val);
                T = T->right;
            }
        }
        return vec;
    }
    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vec.clear();
        TreeNode *T = root, *last = NULL;
        while (T || !st.empty()) {
            if (T) {
                st.push(T);
                T = T->left;
            } else {
                T = st.top();
                if ((!T->left && !T->right) || (T->left == last && !T->right)
                    || (T->right == last)) {
                    vec.push_back(T->val);
                    last = T, T = NULL;
                    st.pop();
                } else {
                    T = T->right;
                }
            }
        }
        return vec;
    }
};

最后的最后，二叉树的遍历还有个空间复杂度的为O(1)的Morris算法，没有使用栈来实现，而是使用了线索二叉树的概念，也是十分巧妙的，有兴趣的童鞋可以Google一下。

OK，就到这里了。如果以上程序有什么错误，欢迎大牛批评指出。