Morris Traversal

• 1968年，Knuth提出说能否将该问题的空间复杂度压缩到O(1)，同时原树的结构不能改变。

• 大约十年后，1979年，Morris在"Traversing Binary Trees Simply and Cheaply"这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

  # Inorder Demo Morris Traversal
  class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        res = []
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                # 1 Find Inorder Predecessor of cur
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right
  
                # 2 Connect or Restore the Pointer
                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    res.append(cur.val)
                    cur = cur.right
        return res