输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
解题思路:
因为是二叉搜索树,和排序相关的首先想到的是中序遍历,因此此题应该建立在中序遍历的基础上,对树的结构进行改造。
我们使用两个指针来辅助完成改造,分别是 $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)$ 的栈空间。
评论区