剑指Offer36二叉搜索树与双向链表
题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
思路：
二叉搜索树，很容易就会想到使用中序遍历，然后在中序遍历的过程中，使用左指针指向前驱，右指针指向后继。
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
版权声明：本文为ntnmywyx原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。