3 ms c++ solution


  • 1
    P
    vector<int> postorderTraversal(TreeNode *root) {
            vector<int> res;
            if (!root) return res;
            stack<TreeNode*> st;
            st.push(root);
            TreeNode* last = NULL;
            while(!st.empty()) {
                TreeNode* top = st.top();
                // pop the node if its a leaf or the last popped node was its right child or 
                // the right child was null and last popped node was left child
                bool popNode = (last && (top->right==last || (top->left==last && !top->right))) || (!top->right && !top->left);
                if (popNode) {
                    last = top;
                    res.push_back(top->val);
                    st.pop();
                } else {
                    if (top->right) st.push(top->right);
                    if (top->left) st.push(top->left);
                }
            }
            return res;
        }

Log in to reply
 

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