Is there a Morris method for this question?


  • 0
    X

    I just wonder if it is possible that this problem can be solved without stacks. Anyone fill me in!


  • 1
    V

    It can be implemented using threaded tree and stacks if the input tree shouldn't be modified, if tree can be modified then with out using threaded tree and stacks it can be achieved.

    Here is the outline of method This link might help:

    Method 1 Without modifying tree using threads and stacks.

    `Post order`: a dummy node created that has root as left descendant.
    
    • A variable can be used to check type of current action. 
    
    • If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
    
    • If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
    
    • If action is visiting node: current node is visited, afterwards its post order successor has to be found.
    
    • If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
    
    • If current node has no right descendant, this is the end of the right-extended chain of nodes.
    
    • First: the beginning of the chain is reached through the thread of the current node.
    
    • Second: right references of nodes in the chain is reversed.
    
    • Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings
    

    Method 2 Modifying tree

    • Changes: reassign some pointers.
    
    • Tree might lose temporarily tree structure, needs to be restored before traversal finished.
    
    • Algorithm, due to J. Morris, for in order traversal.
    
    • If tree has no left successors, in order trivial.
    
    • Temporarily transforms the tree so no left sub tree. Has to keep information to restore it.
    
    • Transformation: make current node the right child of the rightmost node in its left descendant.
    
    • We retain the left pointer of the node moved down right sub tree
    

    Link to reference


  • 0
    J

    C++ version for reference:

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> result;
            if (root == NULL) return result;
            TreeNode* fakeRoot = new TreeNode(0);
            fakeRoot->left = root;
            root = fakeRoot;
            while (root != NULL) {
                while (root->left != NULL) {
                    TreeNode* wormhole = root->left;
                    while (wormhole->right != NULL && wormhole->right != root) {
                        wormhole = wormhole->right;
                    }
                    if (wormhole->right == NULL) {
                        wormhole->right = root;  // dirty
                    } else {
                        wormhole->right = NULL;  // recover
                        reverse(root->left);
                        collect(wormhole, result);
                        reverse(wormhole);
                        break;  // left tree is traversed
                    }
                    root = root->left;
                }
                root = root->right;  // may be a wormhole
            }
            fakeRoot->left = NULL;
            delete fakeRoot;
            return result;
        }
        void reverse(TreeNode* head) {
            TreeNode* prev = NULL;
            TreeNode* next = NULL;
            while (head != NULL) {
                next = head->right;
                head->right = prev;
                prev = head;
                head = next;
            }
        }
        void collect(TreeNode* head, vector<int> &result) {
            while (head != NULL) {
                result.push_back(head->val);
                head = head->right;
            }
        }
    };

Log in to reply
 

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