题解 | #实现二叉树先序，中序和后序遍历#

使用递归法实现先序，中序，后序遍历。由于借助了3个辅助队列，空间复杂度为O(3n)，这里较为容易优化，直接在结果数组上修改的话可将空间复杂度降为O(1)。而对树进行了三次递归，所以 时间复杂度为O(3n)，基本符合题目要求的O(n)。

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<int> first;
        vector<int> mid;
        vector<int> last;
        vector<vector<int>> result;
        if(!root == NULL){
            goFirst(root, first);
            goMid(root, mid);
            goLast(root, last);
        }
        result.push_back(first);
        result.push_back(mid);
        result.push_back(last);
        return result;
    }
    void goFirst(TreeNode* root, vector<int>& first){
        first.push_back(root->val);
        if(root->left != NULL){
            goFirst(root->left, first);
        }
        if(root->right != NULL){
            goFirst(root->right,first);
        }
    }
    void goMid(TreeNode* root, vector<int>& mid){
        if(root->left != NULL){
            goMid(root->left, mid);
        }
        mid.push_back(root->val);
        if(root->right != NULL){
            goMid(root->right,mid);
        }
    }
    void goLast(TreeNode* root, vector<int>& last){
        if(root->left != NULL){
            goLast(root->left, last);
        }
        if(root->right != NULL){
            goLast(root->right,last);
        }
        last.push_back(root->val);
    }
};