O(n) time, O(1) space with Morris Traversal.


  • 4
    G
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> result;
            TreeNode *curr = root, *prev = NULL;
            
            while (curr)
            {
                if (curr->right)
                {
                    prev = curr->right;
                    while (prev->left && prev->left != curr)
                    {
                        prev = prev->left;
                    }
                    
                    if (prev->left)
                    {
                        prev->left = NULL;
                        curr = curr->left;
                    }
                    else
                    {
                        prev->left = curr;
                        result.push_back(curr->val);
                        curr = curr->right;
                    }
                }
                else
                {
                    result.push_back(curr->val);
                    curr = curr->left;
                }
            }
            
            reverse(result.begin(), result.end());
            return result;
        }
    };
    

    Combination of Morris Traversal and a creative postorder traversal from this post: https://discuss.leetcode.com/topic/44387/preorder-inorder-postorder-iterative-solution-by-c


Log in to reply
 

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