Share my clear nonrecursive solution .


  • 0
    A
    class Solution {
        typedef struct REC{
            TreeNode *cur;
            char state;
            REC(TreeNode *ncur, char nstate)
            {
                cur = ncur;
                state = nstate;
            }
        }REC;
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            stack<REC> sta;
            sta.push(REC(root,0));
            while(!sta.empty())
            {
                TreeNode *cur = sta.top().cur;
                char &state = sta.top().state;
                if(!cur)
                    sta.pop();
                else if(state == 0)
                {
                    sta.push(REC(cur->left,0));
                    state = 1;
                }
                else if(state == 1)
                {
                    sta.push(REC(cur->right,0));
                    state = 2;
                }
                else if(state ==2)
                {
                    res.push_back(cur->val);
                    sta.pop();
                }
            }
            
            return res;
            
            
        }
        vector<int> res;
    };

Log in to reply
 

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