Talk is cheap.
func convert(root *TreeNode) *TreeNode {
if root == nil { return root }
var pre, node *TreeNode
stack := []*TreeNode{}
for len(stack) != 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
node, stack = stack[len(stack)-1], stack[:len(stack)-1]
node.Left = pre
if pre != nil {
pre.Right = node
}
pre = node
root = node.Right
}
head := pre
for head.Left != nil {
head = head.Left
}
return head
}