less effective but easy to understand C++ solution


  • 0
    N

    inspired by "data Task = Enqueue val | PushStack node" idea, unfortunately there's no type constructor in C++.
    use a boolean variable to identify if the "task" is to enqueue the node value or expand the current node.

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            stack_.push_back(Item(false,root,0));
            while (!stack_.empty()){
                Item i=stack_.back();
                stack_.pop_back();
                if (i.fake){
                    res_.push_back(i.val);
                }
                else if (i.node==nullptr){
                    continue;
                }
                else {
                    stack_.push_back(Item(true,nullptr,i.node->val));
                    stack_.push_back(Item(false,i.node->right,0));
                    stack_.push_back(Item(false,i.node->left,0));
                }
            }
            return res_;
        }
        struct Item{
            Item(bool fake, TreeNode*node, int val)
                :fake(fake),node(node),val(val)
            {
                
            }
            bool fake;
            TreeNode* node;
            int val;
        };
        vector<int> res_;
        vector<Item> stack_;
    };
    

Log in to reply
 

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