【面试题36 二叉搜索树与双向链表】

难度： 中等

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

Leetcode题目对应位置： 面试题36：二叉搜索树与双向链表

思路：首先很容易想到，① 二叉搜索树的中序遍历序列是递增的，且最左的叶子节点是最小值，对应链表的头节点，最右的叶子节点是最大值，对应链表的尾节点，所以转换过程肯定是 递归的中序遍历。② 要构建双向循环链表，就需要维护两个指针，一个指向前驱节点，一个指向后继节点，对两节点直接进行双向链接后向上层递归。③ 对于 “循环”，需要将头节点和尾节点连起来，所以在递归结束后，要对头、尾节点的链接进行单独处理。

中序遍历：

• 递归左子树，root 表示当前节点
• 当 root.left 不为空时，表示当前节点有前置节点，对两者的链接关系进行修改：root.left = pre, pre.right = root，然后更新 pre = cur
• 当 root.lelft 为空时，表示当前节点是链表头节点，用 head 指向
• 递归右子树
• 递归边界：当 root 为空时，表示越过叶子节点，直接 return

时间复杂度：O(n)，n 为二叉树的节点数
空间复杂度：O(n)，最差情况下二叉树退化为链表，需要 O(n) 的递归调用空间。

class Solution:def treeToDoublyList(self, root: 'Node') -> 'Node':def dfs(cur):if not cur: returndfs(cur.left) # 递归左子树if self.pre: # 修改节点引用self.pre.right, cur.left = cur, self.preelse: # 记录头节点self.head = curself.pre = cur # 保存 curdfs(cur.right) # 递归右子树if not root: returnself.pre = Nonedfs(root)self.head.left, self.pre.right = self.pre, self.headreturn self.head

代码来源：mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/