leetcode 두 갈래 트리 비귀속 반복

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/(앞의 순서 반복)

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        
        vector res;
        stack s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* top = s.top();
            s.pop();
            res.push_back(top->val);
            if (top->right)
                s.push(top->right);
            if (top->left)
                s.push(top->left);
        }
        
        return res;
    }
};

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/(중순 반복)

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        
        vector res;
        stack s;
        TreeNode* cur = root;
        while(!s.empty() || cur != NULL)
        {
            if (cur != NULL)
            {
                s.push(cur);
                cur = cur->left;
            }
            else
            {
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        
        return res;
    }
};

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/(뒷 순서 반복)

//  （ -> -> ， ）
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        
        vector res;
        stack s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* top = s.top();
            s.pop();
            res.push_back(top->val);
            if (top->left)
                s.push(top->left);            
            if (top->right)
                s.push(top->right);
        }        
        
        reverse(res.begin(), res.end());
        return res;        
    }
};

//  ( )
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        
        vector res;
        stack s1;
        stack s2;
        s1.push(root);
        while(!s1.empty())
        {
            TreeNode* top = s1.top();
            s1.pop();
            s2.push(top);
            if (top->left)
                s1.push(top->left);            
            if (top->right)
                s1.push(top->right);
        }
        while(!s2.empty())
        {
            TreeNode* top = s2.top();
            s2.pop();
            res.push_back(top->val);
        }
        
        return res;        
    }
};

// （ ， ）
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        
        vector res;
        stack s;
        TreeNode *cur = root;
        TreeNode *last = NULL;
        while(!s.empty() || cur)
        {
            if (cur)            
            {
                s.push(cur);
                cur = cur->left;
            }
            else
            {
                TreeNode *temp = s.top();
                if (temp->right != NULL && temp->right != last)
                {
                    cur = temp->right;
                }
                else
                {
                    res.push_back(temp->val);
                    last = temp;
                    s.pop();
                }
            }
        }        
        

        return res;        
    }
};