c++ solution with stack and pruning


  • 0

    This solution is fine if we don't mind changing the tree.

        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ans;
            if (!root)
                return ans;
            stack<TreeNode*> s;
            TreeNode* current = root;
            while (true) {
                if (current->left) {
                    TreeNode* thisNode = current;
                    current = current->left;
                    thisNode->left = NULL;
                    s.push(thisNode);
                }
                else if (current->right) {
                    TreeNode* thisNode = current;
                    current = current->right;
                    thisNode->right = NULL;
                    s.push(thisNode);
                }
                else {
                    ans.push_back(current->val);
                    if (s.empty())
                        break;
                    else {
                        current = s.top();
                        s.pop();
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

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