My elegant c++ solution, use stack and a bool flag, without destroying the tree structure


  • 0
    1
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> result;
        if(!root) return result;
        stk.push(root);
        bool flag=false; //whether the children of current node has been checked or not;
        while(!stk.empty()){
            auto tmp= stk.top();
            stk.pop();
            if(!tmp->left and !tmp->right){ //leaf node, pop out directly
                result.push_back(tmp->val);
                if(stk.empty());
                else{
                    if(stk.top()->left==tmp or stk.top()->right==tmp)//check whether the top node's children has been checked or not
                        flag=true;
                    else flag=false;
                }
            }
            else{
                if(flag){   //current node has been checked
                     result.push_back(tmp->val);
                     if(stk.empty());
                     else{
                        if(stk.top()->left==tmp or stk.top()->right==tmp) //check whether the top node's children has been checked or not
                            flag=true;
                        else flag=false;
                     }
                }
                else{    //current node's children have not been checked;
                      stk.push(tmp);
                      if(tmp->right){
                          stk.push(tmp->right);
                          tmp->right=NULL;
                      }
                      if(tmp->left){
                      stk.push(tmp->left);
                      tmp->left=NULL;
                      }
                    flag=false;
                }
            }
        }
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.