Python: Morris Iterator and Normal Iterator. Question(solved now) is why it is TLE if I uncomment the "break". Be careful when using morris traversal since you cannot break in midway.


  • 0

    Morris iterator and normal iterator solution.

    On my own computer they work both well.

    However, in the online judge system, if you uncomment the "break" line, the online system reports TLE. It only happens when I use Morris Iterator.

    I cannot figure out why.
    Who can help me with it?

    Thanks a lot!

    
    class Solution(object):
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            
            ## Morris Traversal (O(n))
            def inOrderIter_Morris(cur):
                while cur:
                    if not cur.left:
                        yield cur
                        cur = cur.right
                    else:
                        # find the predecesser of cur
                        pred = cur.left
                        while pred.right and pred.right != cur: # make sure it is not a loop which means it is visited
                            pred = pred.right
                        if not pred.right:
                            pred.right = cur
                            cur = cur.left
                        else:   
                            yield cur
                            cur = cur.right
                            pred.right = None
                       
            ## use recursive iterator, not sure about the memory usage. (O(n)?)
            def inOrderIter(root):
                if root:
                    for node in inOrderIter(root.left):
                        yield node
                    yield root
                    for node in inOrderIter(root.right):
                        yield node
            
            # main: find the one or two unordered pairs and swap them
            prev, first = None, None
            for node in inOrderIter_Morris(root):
            # for node in inOrderIter(root):
                if prev and prev.val > node.val:
                    if not first:
                        first = prev
                        second = node
                    else:
                        second = node
                        #break # if you uncomment this line you'll get TLE
                prev = node
            first.val, second.val = second.val, first.val

  • 0

    I kind of figured out why. If I use break, the modified tree will not be restored so the judge system cannot judge it due to the loop in the tree.


  • 0

    We need to be very careful when we use morris traversal since it modifies the tree, which means we could only do a complete traversal without break. Make sure to restore it.


Log in to reply
 

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