C++ Iterative solution, one stack


  • 1
    O
    class Solution {
    public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> postorder;
    
        stack<pair<TreeNode*, int>> dfs;
        dfs.push(make_pair(root, 0));
    
        while(!dfs.empty()){
            if (dfs.top().first == NULL) dfs.pop();
            else if (dfs.top().second == 0){
                dfs.top().second++;
                dfs.push(make_pair(dfs.top().first->left, 0));
            }
            else if (dfs.top().second == 1){
                dfs.top().second++;
                dfs.push(make_pair(dfs.top().first->right, 0));
            }
            else if (dfs.top().second == 2){
                postorder.push_back(dfs.top().first->val);
                dfs.pop();
            }
        }
    
        return postorder;
    }
    };

Log in to reply
 

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