[剑指offer] 36. 二叉搜索树与双向链表

题目

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

需要返回双向链表最左侧的节点。

思路 1

1. 排序链表：利用二叉搜索树的中序遍历为递增序列，从小到大访问节点
2. 双向链表：构造链表时，需要规定前驱节点 pre ，并且 pre.right = cur 的同时也要 cur.left = pre
3. 循环链表：构造双向链表时记录头尾节点，构造完成后设置 head.left = tail 和 tail.right = head

因此，使用中序遍历访问树的各节点 cur ；并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；中序遍历完成后，构建头节点和尾节点的引用指向。

注意：

中序遍历若采用递归，一定要有终止条件，其他的遵从递归框架

这道题有特例，root 为空时，直接返回，不能按照正常流程走

参考 Krahets - leetcode

代码

Version 1

class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        def inorder(node):
        	# BT递归框架不变
            if not node: return 
            inorder(node.left)
            # 对于 node 做什么写在这里，其余交给框架
            if self.pre:
                self.pre.right, node.left = node, self.pre
            else:
                self.head = node  # self.pre == None, 标记此时的 cur 为head
            self.pre = node       # 用于下次双向连接
            inorder(node.right)

        if not root: return   ### 漏了这句就错！因为是特例，此时没有self.head 以及 self.head.left ...
        self.pre = None
        inorder(root)
        self.head.left, self.pre.right = self.pre, self.head # 最后一次存储的self.pre就是tail
        return self.head
           

关于 self 的使用：

可以将加 self. 的变量理解为“类的成员变量”， 可以在方法中直接定义，这样就能在类的其他方法里共用了。本题中，由于中序遍历完还需要用到 pre 去实现循环链表，因此我们采用 self.pre ，使其在外部和内部函数中都可以正常访问 ~

诸如 pre = ListNode() , a = 1 等变量，如果想在内外层函数里共用，都必须加 self ，加 self 能限定处理的是同一个对象的参数，如果不加 self 而采用函数传参的方式，每次函数迭代处理的实际上是局部变量，内层函数退出后该变量结果不被保留。另外，list类型的参数可以不加 self，因为函数传递过程中传递的是列表的引用，也就是说在递归的过程中，操作的都是同一个内存空间的list，可以不加self。

复杂度分析：

时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。

空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间。

Version 2

先完成中序遍历，拿到递增序列（序列中节点的存储形式是Node而非val，因为后面需要用到node.left/right …）

然后遍历序列，对每一个节点执行变为双向链表的操作

最后连接头节点和尾节点，变为循环双向排序链表

容易理解，时空复杂度逊于 Version1

class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.res.append(node) # 后面需要用到node.left/right，因此作为Node存储
            inorder(node.right)

        if not root:
            return
        self.res = []
        inorder(root)
        for i, node in enumerate(self.res[:-1]):
            node.right = self.res[i + 1]
            self.res[i + 1].left = node
        self.res[0].left, self.res[-1].right = self.res[-1], self.res[0] # 循环链表
        return self.res[0]