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

Lin2J
2021-07-21 / 0 评论 / 79 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$ 的栈空间。