【链表】打卡10：将搜索二叉树转换成双向链表

发表于 | 更新于 | 分类于 > | 次阅读
将搜索二叉树转换成双向链表

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

对于二叉树的结点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的结点来说，有本身的值域，有指向上一个结点和下一个结点的指针。在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。
　
结点定义：

1
2
3
4
5
6
7
8
class NodeDoubly{
    public int value;
    public NodeDoubly left;
    public NodeDoubly right;
    public NodeDoubly(int value) {
        this.value = value;
    }
}

例如：

这棵二叉搜索树转换后的双向链表从头到尾依次是 1～9。对于每一个结点来说，原来的 right 指针等价于转换后的 next 指针，原来的 left 指针等价于转换后的 last 指针，最后返回转换后的双向链表的头结点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

解答

方法一：采用队列辅助

如果用一个队列来辅助的话，还是挺容易。采用中序遍历的方法，把二叉树的结点全部放进队列，之后在逐一弹出来连接成双向链表。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static NodeDoubly convertUseQueue(NodeDoubly head) {
    if(head == null){
        return head;
    }
    Deque<NodeDoubly> queue = new ArrayDeque<NodeDoubly>();
    //将结点按照中序遍历放进队列里面
    inOrderToQueue(head,queue);
    head = queue.poll();
    NodeDoubly pre = head;
    pre.left = null;
    NodeDoubly cur = null;
    while(!queue.isEmpty()){
        cur = queue.poll();
        pre.right = cur;
        cur.left = pre;
        pre = cur;
    }
    pre.right = null;
    return head;
}

private static void inOrderToQueue(NodeDoubly head, Deque<NodeDoubly> queue) {
    if(head == null){
        return;
    }
    inOrderToQueue(head.left,queue);
    queue.offer(head);
    inOrderToQueue(head.right, queue);
}

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args) {
    NodeDoubly head = new NodeDoubly(6);

    head.left = new NodeDoubly(4);
    head.left.left = new NodeDoubly(2);
    head.left.right = new NodeDoubly(5);
    head.left.left.left = new NodeDoubly(1);
    head.left.left.right = new NodeDoubly(3);

    head.right = new NodeDoubly(7);
    head.right.right = new NodeDoubly(9);
    head.right.right.left = new NodeDoubly(8);
    NodeDoubly doubleLinkedList = convertUseQueue(head);
    NodeDoubly cur = doubleLinkedList;
    while(cur.right!=null){
        System.out.print(cur.value+" ");
        cur = cur.right;
    }
    System.out.print(cur.value);
    System.out.println();
    while(cur!=null){
        System.out.print(cur.value+" ");
        cur = cur.left;
    }
}

方法2：通过递归的方式

在之前打卡的9道题中，几乎超过一半都用到了递归，如果这些题目使用的递归大家都理解了，并且能够自己独立写出代码了，那么我相信大家对递归的思想、使用已经有一定的熟练性。

我们假设函数convert的功能就是把二叉树变成双向链表，例如对于这种一棵二叉树：

经过convert转换后变成这样：

注意：转换之后，把最右边结点的right指针指向了最左边的结点的。

对于下面这样一颗二叉树：

采用convert函数分别对左右子树做处理，结果如下：

之后，再把他们连接起来

了解了基本原理之后，直接看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static NodeDoubly conver(NodeDoubly head) {
    if (head == null) {
        return head;
    }
    //head=2时
    NodeDoubly leftE = conver(head.left);//1的right -> 1
    NodeDoubly rightE = conver(head.right);//3的rigth -> 3
    NodeDoubly leftB = leftE != null ? leftE.right : null;//1
    NodeDoubly rightB = rightE != null ? rightE.right : null;//3
    if (leftE != null && rightE != null) {
        leftE.right = head;
        head.left = leftE;
        head.right = rightB;
        rightB.left = head;
        rightE.right = leftB;
        return rightE;
    } else if (leftE != null) {
        leftE.right = head;
        head.left = leftE;
        head.right = leftB;
        return head;
    } else if (rightE != null) {
        head.right = rightB;
        rightB.left = head;
        rightE.right = head;
        return rightE;
    } else {
        head.right = head;
        return head;
    }
}

时间复杂度为O(n),空间复杂度为O(h)，其中h是二叉树的高度。

运行过程

测试代码

因为返回的是一个环形链表，所以不能使用上面的测试代码进行测试。我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空或者结点为 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void main(String[] args) {
    NodeDoubly head = new NodeDoubly(6);

    head.left = new NodeDoubly(4);
    head.left.left = new NodeDoubly(2);
    head.left.right = new NodeDoubly(5);
    head.left.left.left = new NodeDoubly(1);
    head.left.left.right = new NodeDoubly(3);

    head.right = new NodeDoubly(7);
    head.right.right = new NodeDoubly(9);
    head.right.right.left = new NodeDoubly(8);
    NodeDoubly doubleLinkedList = conver(head);
    NodeDoubly cur = doubleLinkedList;
    Set<NodeDoubly> set = new HashSet<NodeDoubly>();
    while(cur!=null){
        if(set.contains(cur)){
            break;
        }
        set.add(cur);
        System.out.print(cur.value+" ");
        cur = cur.right;
    }
}

原理虽然不难，但写起代码，还是有挺多细节需要注意的，所以一直强调，有时间的话，一定要自己手打一遍代码，有时你以为自己懂了，可能在写代码的时候，发现自己并没有懂，一写就出现很多bug。

来源：苦逼的码农（ID:di201805）

（完）
谢谢你请我吃糖果！
0%