36 二叉搜索树与循环双向链表

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

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

解题思路：

因为是二叉搜索树，和排序相关的首先想到的是中序遍历，因此此题应该建立在中序遍历的基础上，对树的结构进行改造。

我们使用两个指针来辅助完成改造，分别是 $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)$ 的栈空间。