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

题目描述

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

为了让您更好地理解问题，以下面的二叉搜索树为例：

     4
    / \
   2   5
  / \
 1   3

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意：此题对比原题有改动。

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof

解题思路

容易想到使用中序遍历来完成二叉搜索树的链表转换。
核心的思考点是，使用中序遍历，上面例子的3怎么连接4？5怎么连接1？怎么在函数的末尾返回1？
在使用中序遍历的时候，先遍历3再遍历到4。因此想要3连接4，需要在node.val为4的时候，设置一个pre指针指向3，然后让pre.right = node, node.left = pre。
同理，由于中序遍历是从小遍历到大，因此始终让pre为上一个遍历的node，然后pre.right = node, node.left = pre即可。pre需要之后更新为当前node。
因为1必然是二叉搜索树的最小节点，5必然是二叉搜索树的最大节点，因此可以记录min_node和max_node，然后让这两个node互相指向，最后函数返回min_node。

解题代码

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        self.min_node = root
        self.max_node = root
        # pre是关键点，指向上次遍历到的node。pre要和本次的node连起来，因为pre的right没有连接node，node的left可能没连接pre。
        self.pre = None
        self.traverse(root, None)
        self.max_node.right = self.min_node
        self.min_node.left = self.max_node
        return self.min_node

    def traverse(self, node, pre):
        if not node:
            return node
        self.traverse(node.left, node)
        if node.val < self.min_node.val:
            self.min_node = node
        if node.val > self.max_node.val:
            self.max_node = node
        if self.pre: # 第一次进入本函数的时候pre为None
            self.pre.right = node
            node.left = self.pre
        self.pre = node
        self.traverse(node.right, node)

执行结果

执行结果：通过
执行用时：40 ms, 在所有 Python3 提交中击败了40.85%的用户。
内存消耗：15.8 MB, 在所有 Python3 提交中击败了90.89%的用户。