class Solution:
    def Convert(self, root):
        # write code here
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            if self.pre:
                self.pre.right, cur.left = cur, self.pre
            else:
                self.head = cur
            self.pre = cur
            dfs(cur.right)

        if not root: return
        self.pre = None
        dfs(root)
        return self.head