[C++] "Real" Iterative Postorder Traversal without Reverse, using Stack


  • 0
    W
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            stack<TreeNode*> stk;
            vector<int> res;
            if (root == NULL) {
                return res;
            }
            stk.push(root);
            TreeNode *cur, *last = NULL;
            while (!stk.empty()) {
                cur = stk.top();
                if ((last != NULL && (last == cur -> left || last == cur -> right)) || (cur -> left == NULL && cur -> right == NULL)) {
                    res.push_back(cur -> val);
                    last = cur;
                    stk.pop();
                }
                else {
                    if (cur -> right != NULL) {
                        stk.push(cur -> right);
                    }
                    if (cur -> left != NULL) {
                        stk.push(cur -> left);
                    }
                }
            }
            return res;
        }
    };

Log in to reply
 

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