题解 | #二叉搜索树与双向链表#

用list存储中序遍历结果在顺序连接起来，但是这样做空间复杂度是O(N)，看了解题思路，需要在中序遍历过程中改变指针指向，之后来尝试下。

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        self.res = []
        # 中序bianli
        self.midtra(pRootOfTree)
        if len(self.res)==0:
            return None
        root = self.res[0]
        pre = None 
        if len(self.res) == 1:
            return self.res[0]
        for i in range(len(self.res)-1):
            self.res[i].left = pre 
            self.res[i].right = self.res[i+1]
            pre=self.res[i]
        self.res[-1].left = self.res[i]
        return root

    def midtra(self,root):
        # 中序遍历
        if root==None:
            return 
        self.midtra(root.left)
        self.res.append(root)
        self.midtra(root.right)

root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)
root = Solution().Convert(root)
cur=root
while cur:
    print(cur.val)
    cur = cur.right