두 갈래 트리 앞 순서 중 순서 뒤 순서 반복 (비귀속)

두 갈래 나무가 앞뒤로 두루 다니다

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> arr;
        stack<TreeNode*> sa;
        while(!sa.empty()||root){
            while(root){
                sa.push(root);
                arr.push_back(root->val);
                root=root->left;
            }
            if(!sa.empty())
            {
            	root=sa.top()->right;
                sa.pop();
            }
        }
        return arr;
    }
};

두 갈래 나무 사이를 두루 다니다

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> arr;
        stack<TreeNode*> sa;
        while(!sa.empty()||root){
            while(root){
                sa.push(root);
                root=root->left;
            }
            if(!sa.empty())
            {
                arr.push_back(sa.top()->val);
                root=sa.top()->right;
                sa.pop();
            }
        }
        return arr;
    }
};

두 갈래 나무 뒤가 두루 다니다

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> arr;
        stack<TreeNode*> sa;
        vector<int> maze;
        while(!sa.empty()||root)
        {
            while(root)
            {
                sa.push(root);
                maze.resize(sa.size()+1);
                maze[sa.size()]=0;
                root=root->left;    
            }
            while(!sa.empty()&&maze[sa.size()]==1)// 
            {
                root=sa.top();
                arr.push_back(root->val);
                sa.pop();
                root=NULL;
            }
            if(!sa.empty())
            {
                maze[sa.size()]=1;// 
                root=sa.top()->right;
            }
        }
        return arr;
    }
};