leetcode链表之二叉搜索树与双向链表

剑指Offer36二叉搜索树与双向链表

题目：

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

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

flowchart TD
A((4))
B((2))
C((1))
D((3))
E((5))
A-->B
B-->C
A-->E
B-->D

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

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

flowchart LR
head-.-1
1-->2
1-->5
2-->1
2-->3
3-->2
3-->4
4-->3
4-->5
5-->4
5-->1

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

思路：

二叉搜索树，很容易就会想到使用中序遍历，然后在中序遍历的过程中，使用左指针指向前驱，右指针指向后继。

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return root
        node = root
        stack = []
        # 虚拟结点，方便进行操作
        cur = vRoot = Node(0)
        # 中序遍历
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            # 当前指针的right指针指向后继结点，并设置前驱结点为当前结点，当前结点后移
            cur.right = node
            node.left = cur
            cur = cur.right

            node = node.right
                # 遍历完成后，将最后一个结点和第一个结点进行相连
        cur.right = vRoot.right
        vRoot.right.left = cur
        return vRoot.right