剑指offer-二叉树搜索树与双向链表25

题目描述

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

class Solution:

    def Convert(self, pRootOfTree):

        # write code here

        head=None

        pre=None

        s=[]

        while pRootOfTree or len(s) is not 0:

            while pRootOfTree:

                s.append(pRootOfTree)

                pRootOfTree=pRootOfTree.left

            if len(s) is not 0:

                pRootOfTree=s.pop(-1)

                if pre is not None:

                    pre.right=pRootOfTree

                    pRootOfTree.left=pre

                else:

                    head=pRootOfTree

                pre=pRootOfTree

                pRootOfTree=pRootOfTree.right

        return head