输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
解题思路：
因为是二叉搜索树，和排序相关的首先想到的是中序遍历，因此此题应该建立在中序遍历的基础上，对树的结构进行改造。
我们使用两个指针来辅助完成改造，分别是 $pre$ 和 $head$。
- $pre$ 指向的是当前操作节点的前驱节点，在未经过最左节点时，$pre$ 都是处于 $null$ 的状态。之后，$pre$ 都会指向最近经过的节点。
- $head$ 是整个链表的表头，一开始也为 $null$。$head$ 应当指向二叉搜索树的最左节点，因为它是最小的。
中序遍历函数
递归参数： 当前节点 $root$。
终止条件：$root$ 为 $null$ 时，表示整棵树已经遍历完毕，返回。
递归工作：
- 遍历 $root$ 的左子树。
- 如果 $pre$ 不为 $null$，则将 $pre.left$ 指向 $root$，$root.right$ 指向 $pre$，前后驱节点互指。
- 如果 $head$ 为 $null$，则将 $head$ 指向 $root$。
- $pre$ 指向 $root$。
- 遍历 $root$ 的右子树。
经过中序遍历函数之后，$pre$ 会指向最右子节点，$head$ 指向最左子节点。$pre$ 指向链表表尾，$head$ 指向链表表头。
转换函数
- 调用中序遍历函数。
- 将 $pre$ 和 $head$ 互指，即头尾节点互指，$pre.right = head$，$head.left = pre$。
- 返回 $head$。
代码：
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
inorder(root);
// 头尾节点互指
pre.right = head;
head.left = pre;
return head;
}
private void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
if (pre != null) {
pre.right = root;
root.left = pre;
}
if (head == null) {
// head 指向最左节点
head = root;
}
pre = root;
inorder(root.right);
}
复杂度分析
- 时间复杂度$O(N)$：$N$ 为二叉搜索树的节点个数。需要对每个节点进行前后驱节点互指，互指使用 $O(1)$ 时间。
- 时间复杂度$O(N)$：$N$ 为二叉搜索树的节点个数。最差情况下，树退化成链表，进行 $N$ 次递归，需要 $O(N)$ 的栈空间。