Micro-Drill #220 — Morris inorder traversal (O(1) space)

def morrisInorder(root):
    res = []
    cur = root
    while cur:
        if not cur.left:
            res.append(cur.val)
            cur = cur.right
        else:
            # find inorder predecessor
            pred = cur.left
            while pred.right and pred.right != cur:
                pred = pred.right
            if not pred.right:
                pred.right = cur  # create thread
                cur = cur.left
            else:
                pred.right = None  # remove thread
                res.append(cur.val)
                cur = cur.right
    return res