Morris algorithm and clean iterative normal algorithm in Python (29ms)


  • 1

    Morris Algorithm - O(n) time and O(1) space algorithm to traverse the tree

    This algorithm is to change the structure of the tree to find the next node to be traverse, the steps are listed below:

    1. set curNode to root
    2. if curNode.left is None, output curNode.val and set curNode to curNode.right
    3. if curNode.left is not None, find prevNode of curNode in its left subtree
      1. if prevNode.right == None, set prevNode.right to curNode
      2. if prevNode.right == curNode, set prevNode.right back to None, output curNode, and update curNode to curNode.right
    4. loop step 1 and 2 until curNode is None

    Node: preNode of curNode in the Steps refers to the node that is adjacently before curNode in the output list of the inorder traversal of the given tree.

    def inorderTraversal(self, root):
        def _findRightmost(root, parent):
            tmp = root
            while tmp.right and tmp.right != parent:
                tmp = tmp.right
            return tmp
    
        if not root:    return []
        ans = []
        curNode = root
        while curNode:
            if curNode.left:
                prevNode = _findRightmost(curNode.left, curNode)
                if prevNode.right == curNode:
                    prevNode.right = None
                    ans.append(curNode.val)
                    curNode = curNode.right
                else:
                    prevNode.right = curNode
                    curNode = curNode.left
            else:
                ans.append(curNode.val)
                curNode = curNode.right
        return ans
    

    Morris Reference: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

    Clean iterative normal algorithm in Python
    thisNode stores the node that has not been traversed
    stack stores the node whose left sub-tree has been or will be traversed.

    1. if there is a node that has not been traversed at all, we push it into stack and then traverse its left subtree.
    2. if there is no node that has not been traversed at all, then we pop one node from the stack and then start to traverse its right-subtree.
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        thisNode = root # store the node has not been traversed yet
        stack = []      # store the node whose left subtree has been traversed
        ans = []
        while thisNode or stack:
            while thisNode:
                stack.append(thisNode)
                thisNode = thisNode.left
            if stack:
                thisNode = stack.pop(-1)
                ans.append(thisNode.val)
                thisNode = thisNode.right
        return ans
    

Log in to reply
 

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