O(1) O(n)

class Solution(object):
    def convert(self, root):
        if not root:
            return root
        self.pre = None
        self.dfs(root)
        return self.head

    def dfs(self, cur):
        if not cur:
            return 
        self.dfs(cur.left)
        if self.pre:
            self.pre.right = cur
            cur.left = self.pre
        else:
            self.head = cur
        self.pre = cur
        self.dfs(cur.right)