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

前言

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

注：如果代码排版出现了问题麻烦通知我下，谢谢。

【题目描述】

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

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

例如：

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

【要求】

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

【难度】

尉：★★☆☆

【解答】

方法一：采用队列辅助

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

代码如下

 1public static Node2 convert1(Node2 head) {
 2    Queue<Node2> queue = new LinkedList<>();
 3    //将节点按中序遍历放进队列里
 4    inOrderToQueue(head, queue);
 5    head = queue.poll();
 6    Node2 pre = head;
 7    pre.left = null;
 8    Node2 cur = null;
 9    while (!queue.isEmpty()) {
10        cur = queue.poll();
11        pre.right = cur;
12        cur.left = pre;
13        pre = cur;
14    }
15    pre.right = null;
16    return head;
17}
18
19private static void inOrderToQueue(Node2 head, Queue<Node2> queue) {
20    if (head == null) {
21        return;
22    }
23    inOrderToQueue(head.left, queue);
24    queue.offer(head);
25    inOrderToQueue(head.right, queue);
26}

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

方法2：通过递归的方式

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

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

经过conver转换后变成这样：

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

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

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

之后，再把他们连接起来

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

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

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

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