[数据结构与算法]Offer 36. 二叉搜索树与双向链表（中序遍历-中等）

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

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
思路：
? ? 中序遍历（左根右）：前中后序是根据根节点输出位置而言的

? ? 中序遍历 进行访问树节点
? ? 构建相邻节点引用关系时， pre.right = cur ?cur.left=pre
? ? 循环列表 ?head.left = tail tail.right = head

? ? ? ? 4
? ? ? 2 ? 5
? ? 1 ?3

? ? 遍历1 head = pre= cur = node(1)
? ? 遍历2 head=node(1) cur = node(2) ? pre.right=cur cur.left=pre ? ? pre = cur
? ? ……
? ? 遍历5 head=node(1) cur = node(5) ? pre.right=cur cur.left=pre ? ? pre = cur
? ? pre.right = head head.left=pre

ps1:中序遍历递归伪代码

def inorder(root):
    if not root:
        return    
    inorder(root.left)
    print(root.val)
    inorder(root.right)

ps2:对于pre和head这个变量开始想传进去，但是这两个应该是个全局变量。所以最终用了类，然后定义为self.pre self.head，使得inorder和treeToDoublylist都可以用。（对类有点点忘了。。）

复杂度： 时间O(n)? ? ? ? 空间 O(n)

代码：

class Sulotion:
    def treeToDoublyList(self, root):

        def inorder(cur):
            if not cur:
                return

            inorder(cur.left)
            if not self.pre:    # 如果 pre 为None 说明开始遍历第一个  此时仅为 head和pre赋值为当前cur即可
                self.head = cur
            else:
                self.pre.right, cur.left = cur, self.pre    # 构建相邻点关系
            self.pre = cur
            inorder(cur.right)

        if not root:
            return
        self.pre = None
        inorder(root)
        self.pre.right, self.head.left = self.head, self.pre      # 构建首位结点关系
        return self.head

路虽远，行则将至。事虽难，做则必成?。