二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def Convert(self, pRootTree):
        if pRootTree == None:
            return None

        if not pRootTree.left and not pRootTree.right:
            return pRootTree

        self.Convert(pRootTree.left)
        left = pRootTree.left
        if left:
            while left.right:
                left = left.right
            pRootTree.left, left.right = left, pRootTree

        self.Convert(pRootTree.right)
        right = pRootTree.right

        if right:
            while right.left:
                right = right.left

            pRootTree.right, left.right = right, pRootTree

        while pRootTree.left:
            pRootTree = pRootTree.left

        return pRootTree

```go
package main

type TreeNode struct {
    Val    int
    Left   *TreeNode
    Right  *TreeNode
}

func TreeToList(root *TreeNode) (*TreeNode, *TreeNode) {
    head, tail := root, root

    if root == nil {return head, tail}

    if root.Left == nil && root.Right == nil {
        head.Left, tail.Right = root, root
        return root, root
    }

    if root.Left != nil {
        leftHead, leftTail := TreeToList(root.Left)
        head = leftHead
        root.Left = leftTail
        leftTail.Right = root
    }

    if root.Right != nil {
        RightHead, RightTail := TreeToList(root.Right)
        tail = RightTail
        root.RightTail = RightHead
        RightHead.Left = root
    }

}