36. 二叉搜索树与双向链表

class Solution:
  def Convert(self, pRootOfTree):
      # write code here
      if not pRootOfTree:
          return None
      if not pRootOfTree.left and not pRootOfTree.right:
          return pRootOfTree
      #将左子树构建成双链表的表头
      left = self.Convert(pRootOfTree.left)
      cur = left
      #找到当前链表的最后一个节点
      while left and cur.right:
          cur = cur.right
      #如果左子树不为空，将当前的根节点加到左子树右边
      if left:
          cur.right = pRootOfTree
          pRootOfTree.left = cur
      #将右子树构成双链表，返回链表头
      right = self.Convert(pRootOfTree.right)
      #如果右子树不为空，将右子树链接到根节点的右边
      if right:
          right.left = pRootOfTree
          pRootOfTree.right = right
      return left if left else pRootOfTree