题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：采用中序遍历的思路，
1.定义pHead用于记录头节点，用于返回
2.pCur节点用于记录下当前节点的上一个节点，如初始时，pHead=1，Pcur = 1；当访问到2时，Pcur.right=2,2.left = Pcur, 下次节点变换时，需要Pcur = 2
image.png
代码：
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.pHead = None#记录下头指针
self.pCur = None#记录下需要更改变方向的指针，及中序遍历下，当前指针的前一个指针
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree == None:
return
self.Convert(pRootOfTree.left)
if self.pHead ==None:
self.pHead = pRootOfTree
self.pCur = pRootOfTree
else:
self.pCur.right = pRootOfTree
pRootOfTree.left = self.pCur
self.pCur = pRootOfTree
self.Convert(pRootOfTree.right)
return self.pHead
