解法一：递归

「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；

「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；

「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点；

下图以「先序遍历」为例进行展示：

基于上述思路，可以得到实现代码如下：

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

class Solution {
public:
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > res;
    vector<int> preorder, inorder, postorder;
    vector<vector<int> > threeOrders(TreeNode* root) {
        preOrder(root);
        inOrder(root);
        postOrder(root);
        res.push_back(preorder);
        res.push_back(inorder);
        res.push_back(postorder);
        return res;
    }
    void preOrder(TreeNode* root) {
        if (!root) return;
        preorder.push_back(root->val); // 访问根结点
        preOrder(root->left); // 访问左子树
        preOrder(root->right); // 访问右子树
    }
    void inOrder(TreeNode* root) {
        if (!root) return;
        inOrder(root->left); // 访问左子树
        inorder.push_back(root->val); // 访问根结点
        inOrder(root->right); // 访问右子树
    }
    void postOrder(TreeNode* root) {
        if (!root) return;
        postOrder(root->left); // 访问左子树
        postOrder(root->right); // 访问右子树
        postorder.push_back(root->val); // 访问根结点
    }
};

该方法需要遍历二叉树的所有结点，因此时间复杂度为O(N)；

该方法在递归过程中需要使用栈空间，在最坏情况下（二叉树退化为链表），空间复杂度为O(N)。

解法二：非递归

二叉树的三种遍历也可以通过「非递归」的方式实现，其中，先序遍历与中序遍历的非递归实现方式类似，后序遍历实现方式有所不同。

先序遍历过程如图所示，步骤如下：

1. 根结点入栈；
   重复如下操作：
   1. 访问栈顶结点；
   2. 右孩子入栈（若有）；
   3. 左孩子入栈（若有）；

中序遍历过程如图所示，步骤如下：

1. 访问以当前结点p为根结点的「最左孩子」n；
2. 访问n，并将p更新至其右子树上：p = p->right；
3. 若p无右子树，则说明p是某棵子树的根结点，则在下一次循环中访问p；若p有右子树，则按照上述相同步骤访问该右子树，最后访问p。

后序遍历过程如图所示，步骤如下：

1. 定义last指针，用以代表「上次访问的位置」，p结点用来遍历；
2. 由于后续遍历需要先访问左子树和右子树、最后访问根结点，因此在满足如下条件时才能访问该结点：
   1. 该结点没有右子树；
   2. 该结点有右子树，且上次访问的结点（last指针）为其右子树，即该右子树已经被访问过了；
3. 在不满足上述条件的情况下，说明当前结点还不能被访问，故先访问其右子树：p = p->right；
4. 将p结点置为NULL，防止下次while循环时重复访问；

基于上述思路，实现代码如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > res; 
    vector<int> preorder, inorder, postorder; 
    vector<vector<int> > threeOrders(TreeNode* root) {
        preOrder(root); 
        inOrder(root); 
        postOrder(root); 
        res.push_back(preorder); 
        res.push_back(inorder); 
        res.push_back(postorder); 
        return res; 
    }
    void preOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root; 
        s.push(p); 
        while (s.size()) {
            p = s.top(); // 访问根结点
            s.pop(); // 根结点出栈
            preorder.push_back(p->val); 
            if (p->right) s.push(p->right); // 右子树入栈
            if (p->left) s.push(p->left); // 左子树入栈
        }
        return; 
    }
    void inOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root; 
        while (s.size() || p) {
            while (p) { // 寻找最左的孩子
                s.push(p); 
                p = p->left; 
            }
            p = s.top(); 
            inorder.push_back(p->val); // 访问
            s.pop(); 
            p = p->right; // 右子树
        }
        return; 
    }
    void postOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root, *last = NULL; // last记录先前被访问的结点
        while (s.size() || p) {
            while (p) { // 最左的孩子
                s.push(p); 
                p = p->left; 
            }
            p = s.top(); 
            if (!p->right || last == p->right) { // 若该结点没有右孩子，或上一次访问的是右子树，则直接访问该结点
                s.pop(); 
                postorder.push_back(p->val); 
                last = p; // 更新last
                p = NULL; // p置空，防止下一次循环重复访问
            } else {
                p = p->right; // 右子树
            }
        }
    }
};

该方法需要遍历二叉树的所有结点，因此时间复杂度为O(N)；

该方法需要定义、使用栈空间，空间复杂度为O(N)。