Using 'break' causes TLE


  • 0
    M

    use the Morris Inorder traversal and pass the OJ. Now I want to optimize the code by adding 'break' once the second node is found. However, this will cause TLE... I test the case which causes the TLE, the version with 'break' is faster than the version without 'break', and the result is the same. Could anyone explain this?

    class Solution(object):
        def recoverTree(self, root):
            broken = [None, None]
            prev, cur = None, root
            while cur:
                if not cur.left:
                    if prev and cur:
                        if cur.val < prev.val:
                            if not broken[0]:
                                broken[0] = prev
                                broken[1] = cur
                            else:
                                broken[1] = cur
                                break
                    prev, cur = cur, cur.right
                else:
                    p = cur.left
                    while p.right and p.right != cur:
                        p = p.right
                    if p.right != cur:
                        p.right = cur
                        cur = cur.left
                    else:
                        p.right = None
                        if prev and cur:
                            if cur.val < prev.val:
                                if not broken[0]:
                                    broken[0] = prev
                                    broken[1] = cur
                                else:
                                    broken[1] = cur
                                    break
                        prev, cur = cur, cur.right
            broken[0].val, broken[1].val = broken[1].val, broken[0].val
    

Log in to reply
 

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