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

/**
 * 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<>>
     */
    void preTraverse(TreeNode* root, vector<int> &preT){
        //先序遍历————递归法
        if(root == nullptr) return;
        preT.push_back(root->val);
        preTraverse(root->left, preT);
        preTraverse(root->right, preT);
    }
    void preTraverse2(TreeNode* root, vector<int> &preT) {
        //先序遍历————非递归法
        if(root == nullptr) return;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur !=nullptr || !st.empty()){
            if(cur){
                preT.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
    }
    void inTraverse(TreeNode* root, vector<int> &inT){
        //中序遍历————递归法
        if(root == nullptr) return;
        inTraverse(root->left, inT);
        inT.push_back(root->val);
        inTraverse(root->right, inT);
    }
    void inTraverse2(TreeNode* root, vector<int> &inT){
        //中序遍历————非递归法
        if(root == nullptr) return;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur){
                while(cur){
                    st.push(cur);
                    cur = cur->left;
                }
            }else{
                cur = st.top();
                st.pop();
                inT.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    void postTraverse(TreeNode* root, vector<int> &posT){
        //后序遍历————递归法
        if(root == nullptr) return;
        postTraverse(root->left, posT);
        postTraverse(root->right, posT);
        posT.push_back(root->val);
    }
    void postTraverse2(TreeNode* root, vector<int> &posT){
        //后序遍历————非递归法、先序反向
        if(root == nullptr) return;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur){
                posT.push_back(cur->val);
                st.push(cur);
                cur = cur->right;
            }else{
                cur = st.top();
                st.pop();
                cur = cur->left;
            }
        }
        reverse(posT.begin(), posT.end());
    }
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<int> preT;
        vector<int> inT;
        vector<int> posT;
        vector<vector<int>> res;
        /**递归法**/
        preTraverse(root, preT);
        inTraverse(root, inT);
        postTraverse(root, posT);
        /**非递归法
        preTraverse2(root, preT);
        inTraverse2(root, inT);
        postTraverse2(root, posT);
        **/
        //返回
        res.push_back(preT);
        res.push_back(inT);
        res.push_back(posT);
        return res;
    }
};