0 ms Clear C++ solutions --- iterative, recursive, Morris traversal (3 different solutions!)


  • 64

    Hi, this is a fundamental and yet classic problem. I share my three solutions here:

    1. Iterative solution using stack --- O(n) time and O(n) space;
    2. Recursive solution --- O(n) time and O(n) space (considering the spaces of function call stack);
    3. Morris traversal --- O(n) time and O(1) space!!!

    Iterative solution using stack:

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> toVisit;
        TreeNode* curNode = root;
        TreeNode* lastNode = NULL;
        while (curNode || !toVisit.empty()) {
            if (curNode) {
                toVisit.push(curNode);
                curNode = curNode -> left;
            }
            else {
                TreeNode* topNode = toVisit.top();
                if (topNode -> right && lastNode != topNode -> right)
                    curNode = topNode -> right;
                else {
                    nodes.push_back(topNode -> val);
                    lastNode = topNode;
                    toVisit.pop();
                }
            }
        }
        return nodes;
    }
    

    Recursive solution:

    void postorder(TreeNode* root, vector<int>& nodes) {
        if (!root) return; 
        postorder(root -> left, nodes);
        postorder(root -> right, nodes);
        nodes.push_back(root -> val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        postorder(root, nodes);
        return nodes;
    } 
    

    Morris traversal:

    void reverseNodes(TreeNode* start, TreeNode* end) {
        if (start == end) return;
        TreeNode* x = start;
        TreeNode* y = start -> right;
        TreeNode* z;
        while (x != end) {
            z = y -> right;
            y -> right = x;
            x = y;
            y = z;
        }
    }
    void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
        reverseNodes(start, end);
        TreeNode* node = end;
        while (true) {
            nodes.push_back(node -> val);
            if (node == start) break;
            node = node -> right;
        }
        reverseNodes(end, start);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        TreeNode* dump = new TreeNode(0);
        dump -> left = root;
        TreeNode* curNode = dump;
        while (curNode) {
            if (curNode -> left) {
                TreeNode* predecessor = curNode -> left;
                while (predecessor -> right && predecessor -> right != curNode)
                    predecessor = predecessor -> right;
                if (!(predecessor -> right)) {
                    predecessor -> right = curNode;
                    curNode = curNode -> left;
                }
                else {
                    reverseAddNodes(curNode -> left, predecessor, nodes);
                    predecessor -> right = NULL;
                    curNode = curNode -> right;
                }
            }
            else curNode = curNode -> right;
        }
        return nodes;
    }

  • 0
    S
    public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> s = new Stack();
            List<Integer> result = new ArrayList();
            TreeNode curr = root;
            TreeNode lastVisited = null;
            while(!s.isEmpty() || curr != null){
                if(curr != null){
                    s.push(curr);
                    curr = curr.left;
                }
                else{
                    TreeNode peekNode = s.peek();
                    if(peekNode.right != null && peekNode != lastVisited){
                        curr = peekNode.right;
                    }
                    else{
                        lastVisited = s.pop();
                        result.add(lastVisited.val);
                    }
                }
            }
            return result;
        }
    

    Basicly, I use the same idea as your iterative approach, but I got TLE. I don't know why. Can you help? Thank you very much.


  • 1

    if(peekNode.right != null && peekNode != lastVisited){ should be

    if(peekNode.right != null && peekNode.right != lastVisited){.


  • 0
    S

    Oh, thank you so much. Big help~


  • 1
    W

    @jianchao.li.fighter Another solution : ) we can iterate the tree in preorder but little different: root --> right --> left . Than reverse it:

    vector<int> postorderTraversal(TreeNode* root) {
            vector<int> result;
            if(root == NULL) return result;
            stack<TreeNode*> stk;
            stk.push(root);
            while(!stk.empty()) {
                auto cur = stk.top();
                result.push_back(cur->val);
                stk.pop();
                if(cur->left) stk.push(cur->left);
                if(cur->right) stk.push(cur->right);
            }
            reverse(result.begin(), result.end());
            return result;
        }
    

  • 0

    Anyone know how to traverse in post order using Morris traversal in Java?


  • 0
    W
    This post is deleted!

  • 0
    E

    @wangxinbo I'm sorry man, I don't even realize that, it must be a operational error. I have no impression that I downvote your reply. Now I change it. So sorry about that.


  • 0

    @jianchao-li-fighter
    I have noticed that the postorder traversal is left-right symmetric to the preorder traversal!
    Thus, when conducting postorder traversal, you first visit parent node, then the right child tree, last the left child tree.
    However, to get a right answer, you need to inverse the result!
    I have tested the code on OJ, they are accepted!

    As puts here https://discuss.leetcode.com/topic/104897/the-simplest-iterative-morris-solutions-postorder-is-symmetric-to-the-preorder

    Iterative Traversal

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nums;
        stack<TreeNode* > stnode;
        while (root || !stnode.empty()) {
            if (!root) {
                root = stnode.top();
                stnode.pop();
            }
            nums.push_back(root->val);
            if (root->left) stnode.push(root->left);
            root = root->right;
        }
        return vector<int>(nums.rbegin(), nums.rend()) 
    } 
    

    Morris Traversal

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> nums;
            TreeNode* cur = nullptr;
    
            while (root) {
                if (root->right) {
                    cur = root->right;
                    while (cur->left && cur->left != root) {
                        cur = cur->left;
                    }
                    if (cur->left == root) {
                        cur->left = nullptr;
                        root = root->left;
                    } else {
                        nums.push_back(root->val);
                        cur->left = root;
                        root = root->right;
                    }
                } else {
                    nums.push_back(root->val);
                    root = root->left;
                }
            }
            return vector<int>(nums.rbegin(), nums.rend());
        } 
    }

Log in to reply
 

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