一.题目描述
NC45实现二叉树先序，中序和后序遍历
分别按照二叉树先序遍历、中序遍历和后序遍历打印所有的节点。
二.算法(递归实现)
图片说明
以先序遍历来解释，首先我们需要了解什么是二叉树的先序遍历：按照访问根节点-左子树-右子树的方式遍历这棵树，而在访问左子树和右子树的时候我们按照同样的方式遍历，直到遍历整棵树。我们对先序遍历进行进一步分析：

/*
若二叉树是空树，则什么都不做；否则：
(1)访问根节点
(2)先序遍历左子树
(3)先序遍历右子树
*/
void preorder(TreeNode* t){
        if(t!=NULL) return ;
        visit(t);//假设访问函数visit已经访问过来，其中包含看对结点t的各种操作，如打印td
        xian(t->left);//先序遍历左子树
        xian(t->right);//先序遍历右子树
}

我们对先序遍历有了进一步的了解，那么整个题目就简单了，直接看代码:

class Solution {
public:
    //先序遍历
    void preorder(TreeNode* t,vector<int> &ans){//注意这块是& 不然ans的内容无法带回去
        if(!t) return ;
        ans.push_back(t->val);
        preorder(t->left, ans);
        preorder(t->right,ans);
    }
    //中序遍历
    void inorder(TreeNode* t,vector<int> &ans){
        if(!t) return ;
        inorder(t->left, ans);
        ans.push_back(t->val);
        inorder(t->right,ans);
    }
    //后序遍历
    void postorder(TreeNode* t,vector<int> &ans){
        if(!t) return ;
        postorder(t->left, ans);
        postorder(t->right,ans);
        ans.push_back(t->val);
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int>> tree;
        vector<int>q;
        preorder(root,q);//先序
        tree.push_back(q);
        q.clear();//每一次都要将q清空
        inorder(root,q);//中序
        tree.push_back(q);
        q.clear();
        postorder(root,q);//后序
        tree.push_back(q);
        q.clear();
        return tree;
    }
};

时间复杂度:O(n)
空间复杂度:O(n)需要额外开辟空间来存储结果
优缺点:代码长，但是思路简单，实现起来容易。
三.算法(迭代)
我们还是以先序遍历为例子:
图片说明
在迭代算法中，思路演变成，每到一个节点 A，就应该立即访问它。因为，每棵子树都先访问其根节点。对节点的左右子树来说，也一定是先访问根。在A的两棵子树中，遍历完左子树后，再遍历右子树。因此，在访问完根节点后，遍历左子树前，要将右子树压入栈。

栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的右子树入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
}

我们发现后序遍历和前序遍历的思路是一样的但是，中序遍历是否一样呢？？ 很显然中序不同于前序和后序
图片说明
为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢？因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

对于中序和前后序的遍历我们都有了了解那么完整的代码如下:

class Solution {
public:
    //先序遍历
   void preoredr(TreeNode* root,vector<int> &result) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left); 
                st.push(node);
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
    }
    //中序遍历
     void inoredr(TreeNode* root,vector<int> &v) {
        stack<TreeNode*> S;
        TreeNode* rt = root;
        while(rt || S.size()){
            while(rt){
                S.push(rt);
                rt=rt->left;
            }
            rt=S.top();S.pop();
            v.push_back(rt->val);
            rt=rt->right;
        }
    }
    //后序遍历
    void postorder(TreeNode* root,vector<int>& v) {
        stack<TreeNode*> S;
        TreeNode* rt = root;
        while(rt || S.size()){
            while(rt){
                S.push(rt->left);
                v.push_back(rt->val);
                rt=rt->right;
            }
            rt=S.top();S.pop();
        }
        reverse(v.begin(),v.end());
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int>> tree;
        vector<int>q;
        preoredr(root,q);
        tree.push_back(q);
        q.clear();//每次记录后要清除
        inoredr(root,q);
        tree.push_back(q);
        q.clear();
        postorder(root,q);
        tree.push_back(q);
        q.clear();
        return tree;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)
优缺点：实现起来相当的复杂！！所以只是为了锻炼读者的能力，相比于上一种写法这一种的实现难度多。