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

栈+颜色标记法，刷题小能手++

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

#define WHITE 0
#define GRAY 1

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> preoder = preorderVisit(root);
        vector<int> inorder = inorderVisit(root);
        vector<int> postorder = postorderVisit(root);
        return vector<vector<int>>{preoder,inorder,postorder};
    }
    
    vector<int> preorderVisit(TreeNode* root) {
        vector<int> res = vector<int>();
        vector<tuple<int,TreeNode*>> stack =  vector<tuple<int,TreeNode*>>();
        if(root!=nullptr) {
            stack.push_back(tuple<int,TreeNode*>(WHITE,root));
        }
        while (stack.size()>0){
            tuple<int,TreeNode*> top = stack.back();
            stack.pop_back();
            if(std::get<0>(top)==WHITE) {
                TreeNode* current = std::get<1>(top);
                if(current->right!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->right));
                }
                if(current->left!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->left));
                }
                stack.push_back(tuple<int,TreeNode*>(GRAY,current));
            }else{
                res.push_back(std::get<1>(top)->val);
            }
        }
        return res;
    }
    
    vector<int> inorderVisit(TreeNode* root) {
        vector<int> res = vector<int>();
        vector<tuple<int,TreeNode*>> stack =  vector<tuple<int,TreeNode*>>();
        if(root!=nullptr) {
            stack.push_back(tuple<int,TreeNode*>(WHITE,root));
        }
        while (stack.size()>0){
            tuple<int,TreeNode*> top = stack.back();
            stack.pop_back();
            if(std::get<0>(top)==WHITE) {
                TreeNode* current = std::get<1>(top);
                if(current->right!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->right));
                }
                stack.push_back(tuple<int,TreeNode*>(GRAY,current));
                if(current->left!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->left));
                }
            }else{
                res.push_back(std::get<1>(top)->val);
            }
        }
        return res;
    }
    
    vector<int> postorderVisit(TreeNode* root) {
        vector<int> res = vector<int>();
        vector<tuple<int,TreeNode*>> stack =  vector<tuple<int,TreeNode*>>();
        if(root!=nullptr) {
            stack.push_back(tuple<int,TreeNode*>(WHITE,root));
        }
        while (stack.size()>0){
            tuple<int,TreeNode*> top = stack.back();
            stack.pop_back();
            if(std::get<0>(top)==WHITE) {
                TreeNode* current = std::get<1>(top);
                stack.push_back(tuple<int,TreeNode*>(GRAY,current));
                if(current->right!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->right));
                }
                if(current->left!=nullptr) {
                    stack.push_back(tuple<int,TreeNode*>(WHITE,current->left));
                }
            }else{
                res.push_back(std::get<1>(top)->val);
            }
        }
        return res;
    }
    
};