[팁] 두 갈래 나무의 여러 가지 흔적

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

stack S;     // 
        
TreeNode *cur = root;
S.push(cur);
        
while(!S.empty()){
    if(S.top()->left != cur && S.top()->right != cur){  // 
        gotoHLVFL(S);
    }
    // 
    cur = S.top();  S.pop();
    //visit(cur)
}


void gotoHLVFL(stack &S){
    TreeNode *cur;
    while((cur = S.top()) != NULL){
        if(cur->left != NULL){
            if(cur->right != NULL) S.push(cur->right);
            S.push(cur->left);
            // cur = cur->left;
        }else{
            S.push(cur->right);
            // cur = cur->right;
        }
    }
    S.pop();
}

vector postOrder(TreeNode *root)
{
    vector res;
    if(root == NULL) return res;

    TreeNode *p = root;
    stack sta;
    sta.push(p);
    sta.push(p);
    while(!sta.empty())
    {
        p = sta.top(); sta.pop();
        if(!sta.empty() && p==sta.top())
        {
            if(p->right) sta.push(p->right), sta.push(p->right);
            if(p->left) sta.push(p->left), sta.push(p->left);
        }
        else
            res.push_back(p->val);
    }
    
    return res;
}