【面试题27】二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：采用中序遍历的思路，
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