C++ concise solution with memoization


  • 0
    B

    use a set to store visited node, the code would be clean and efficient
    since stack already used O(n) space, it would not bother to use another O(n) space.

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) 
        {
            vector<int> ans;
            if(!root) return ans;
            stack<TreeNode*>stk;
            stk.push(root);
            unordered_set<TreeNode*>visited;
            while(!stk.empty())
            {
                TreeNode * temp = stk.top();
                if(temp -> right && visited.find(temp->right)==visited.end()) stk.push(temp->right);
                if(temp -> left && visited.find(temp->left)==visited.end()) stk.push(temp->left);
                if(temp==stk.top())
                {
                    stk.pop();
                    ans.push_back(temp->val);
                    visited.insert(temp);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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